题目描述

写一个函数，求两个整数之和，要求在函数体内不得使用 ＋、－、×、÷ 四则运算符号。

样例

输入：num1 = 1 , num2 = 2

输出：3

算法

(位运算) $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)$

C++ 代码

class Solution {
public:
    int add(int num1, int num2){
        while (num2)
        {
            int sum = num1 ^ num2;
            int carry = num1 & num2;
            num1 = sum;
            num2 = carry << 1;
        }

        return num1;
    }
};