题目描述

写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。

示例:

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

提示：

• $a$, $b$ 均可能是负数或 0
• 结果不会溢出 32 位整数

---

算法

(位运算) $O(logn)$

1. 首先我们可以将 $num1 + num2 = A + B$，A 是 $num1 + num2$ 做不进位加法的结果，B 是 $num1 + num2$ 产生的进位结果，两部分加起来就是 $num1 + num2$
2. 不进位加法可以用异或 ^，计算进位可以用与 &，对每一位进行这两种操作
3. 因为不能用加法，所以 $A + B$ 可以用 whlie 循环代替
   循环终止条件：由于每次计算进位的结果 $carry$ 会左移 1 位，后面补 0，再计算新的进位做 & 运算时后面的 0 还是 0 不会出现 1，所以在不断的移位后 $carry$ 必然会变成 0，循环可以结束
   循环内部：每次 $num1$ 和 $num2 / carry$ 做不进位加法，计算新产生的进位（为什么会有新的进位，因为 $sum$ 的结果和进位结果做不进位加法后可能还会出现新的进位），直到没有进位为止计算结束，$num1$ 中存的就是 num1 + num2 的结果
4. !注意：此做法只能做正数加法

时间复杂度

进位 $carry$ 每次左移 $1$ 位相当于除以 $2$，$logn$ 次 $carry$ 为 $0$，所以时间复杂度为 $O(logn)$

空间复杂度

$O(1)$

代码

class Solution {
public:
    int add(int a, int b) {
        while (b) {
            int sum = a ^ b;
            int carry = (unsigned int) (a & b) << 1;
            a = sum;
            b = carry;
        }
        return a;
    }
};