371.两整数之和

两数之和

参考

思路

在做 10 进制加法时，例如15 + 6，我们先将低位相加得到结果的低位 1 和进位 1，将进位 1 和高位 1 相加就得到了结果的高位 2，最终的结果为 21。所以求加法的过程中，我们要得到当前位的结果和进位。
推广到二进制，有

0 & 0 = 0, 0 ^ 0 = 0;
0 & 1 = 0, 0 ^ 1 = 1;
1 & 0 = 0, 1 ^ 0 = 1;
1 & 1 = 1, 1 ^ 1 = 0;

我们发现两个二进制位做异或就是相加得到的当前位的结果，做与操作就是进位。

所以，我们将 a, b 进行异或操作得到当前位的结果，进行与操作得到进位，如果进位为0，则退出循环，否则将当前步的结果赋值给 a，将进位左移一位的结果赋值为 b。代码如下：

 public int getSum(int a, int b) {
        if (a == 0) return b;
        if (b == 0) return a;
        int ans = 0;
        int carry = 0;
        while (true) {
            ans = a ^ b;
            carry = a & b;
            if (carry == 0) break;
            a = ans;
            b = carry << 1;
        }

        return ans;
    }

简化

public int getSum1(int a, int b) {
        while(b != 0){
            int temp = a ^ b;
            b = (a & b) << 1;
            a = temp;
        }
        return a;
}