题目描述

计算a,b两数之和，不能用+和-。

样例

Example 1:

输入: a=1,b=2
输出: 3


Example 2:

输入: a=-2,b=3
输出: 1

算法

(位运算) $O(1)$

1. 用<异或>来算不带进位的和(异或：0⊕0=0，1⊕0=1，0⊕1=1，1⊕1=0)
2. 用<与>并<左移>一位来算进位
3. 递归计算<异或>结果(无进位和)和<相与>结果(进位)的和，直到无需进位

举例：

a=101

b=011

第一步异或，$ a \land b = 110 $，最右位的和2需要进位；

第二步相与，$ a \& b = 001 $，相与出来的结果表示的是需要进位的地方，将它左移一位得到$010$；

第三步，递归调用getsum，求$110$和$010$的和。

时间复杂度$O(1)$

空间复杂度$O(1)$

第二行原来的版本是 carry = (a&b)<<1，感谢@zeromagic指出问题：

LeetCode现在增强了这道题的数据。上面的做法已经无法AC。
1. 两个数均为负数时，RE。eg. [-2, -3]
2. 当负数的绝对值小于正数时，RE。eg. [-2, 3]
3. 极限数据，RE。eg. [2147483647, -2147483648]

进行如下强转后可AC。
carry = uint(a & b) << 1;

C++ 代码

class Solution {
public:
    int getSum(int a, int b) {
      if(b == 0) return a;
      int sum = a ^ b, carry = uint(a&b)<<1;
      return getSum(sum,carry);
    }
};