LeetCode 371. Sum of Two Integer

题目

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

Example 1:
Input: a = 1, b = 2
Output: 3

Example 2:
Input: a = -2, b = 3
Output: 1

解析

这是一道面试中常会考到的题目，即不使用operator +/-实现加/减运算。这就涉及到位操作。

与&：有0为0，同1为1；
或|：有1为1，同0为0；
非/取反~：0变1，1变0；
异或^：相同为0，不同为1；
左移<<乘2，右移除2。

上述为基本的操作方法，在本题中加法的操作即是每一位相加，然后如果有进位在上一位的结果中加上该进位，最终加至无进位。
另外，异或操作为不带进位的加法，而进位是在&操作中保留着，因此，a + b的操作可以简化为以下：

while (b):
  c = a ^ b;      // 不带进位的加法
  b = (a & b) << 1;    // a&b是每一位的进位，其进位在上一位，因此需要左移1位
  a = c
// 最终将进位b加完了，a保存结果。

上述代码中注释已经很清晰了，先异或，再与和移位。

代码（C语言）

int getSum(int a, int b) {
    while (b) {
        int c = a ^ b;
        b = (a & b) << 1;
        a = c;
    }
    
    return a;
}