Leetcode371题两数之和

给你两个整数 a 和 b ，不使用 运算符 + 和 - ​​​​​​​，计算并返回两整数之和。

示例 1：

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

示例 2：

输入：a = 2, b = 3
输出：5

提示：
-1000 <= a, b <= 1000
解题代码：

class Solution {
public:
    int getSum(int a, int b) {
        if (!a) return b; // a+b=a^b, (a&b)<<1为零
        int sum = a ^ b, carry = (unsigned)(a & b ) << 1; // 转化为题a+b=a^b + (a&b)<<1。
        return getSum(carry, sum); //递归求解子问题
    }
};

解题思路：
位运算中 ⨁ bigoplus ⨁是不进位的加法运算， a + b a+b a+b可以拆分为不进位部分 + + +进位部分，不进位部分是 a ⨁ b abigoplus b a⨁b，进位可以用 ⋀ bigwedge ⋀符号得到 ( a ⋀ b ) (a bigwedge b) (a⋀b), 进位要加到前面一位所以原问题转化为 a + b = a b + ( a ⋀ b ) < < 1 a+b=a^b + (a bigwedge b)<<1 a+b=ab+(a⋀b)<<1, 因为此时不能使用加号，所有只有当 ( a + b ) < < 1 (a+b)<<1 (a+b)<<1为0时， a + b a+b a+b等于 a ⋁ b a bigvee b a⋁b。
现在考虑一下 a ⋀ b < < 1 a bigwedge b<<1 a⋀b<<1永远不会为0吗，显然是不会的， a ⋀ b < < 1 a bigwedge b<<1 a⋀b<<1,每次最后会多一个零，最多进行32次。