371-两整数之和

LeetCode 371. Sum of Two Integers

Given two integers a and b, return the sum of the two integers without using the operators + and -.

Example 1:

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

method: 递归

通过观察异或运算的真值表，与加法的真值表特别地像。需要注意的是异或只看本位，加法可能需要进位。从而用到与运算&。

与运算可以很好地解决加法进位的问题，加法进位和与运算结果对应：1+0、0+1、0+0的进位都是0，1+1的进位为1
通过异或得到了本位和，通过与运算得到了进位值，最后，只需要将进位值给高一位即可。

建议
对有符号数使用位运算，符号位如何处理没有明确的规定，所以强烈建议仅将位运算符用于处理无符号类型

int getSum(int a, int b) {
    if (!b) return a;
    int sum = a ^ b;    // 相加结果
    int carry = (unsigned)(a & b) << 1; // 进位，转为无符号数
    return getSum(sum, carry);
}

method 2: 迭代

int getSum(int a, int b) {
    int c = 0;
    while (b) {
        c = a & b;  // 存储进位
        a = a ^ b;  // 存储一次相加的结果
        b = (unsigned)c << 1;   // 进位左移一位
    }
    return a;
}