算法笔记之位运算实现加法

看一下使用位运算实现加法运算的题目。

LeetCode 371. 两整数之和

不使用运算符 + 和 - ​​​​​​​，计算两整数 ​​​​​​​a 、b ​​​​​​​之和。

解题思路

在二进制的计算中就是要通过位操作来得到结果的低位和进位，对于不同的情况，用表格来表示一下，两个数字分别为a和b

从上面可以发现，低位 = a^b，进位 = a & b。这样的计算可能要持续多次，回想一下在十进制的计算中，如果进位一直大于0，就得往后面进行计算，在这里也是一
样，只要进位不是0，我们就得一直重复计算低位和进位的操作。

代码实现

最终实现的Java代码如下所示：

class Solution {
    public int getSum(int a, int b) {
        int sum = 0;
        while(b != 0) {
            sum = a ^ b;
            b = (a & b) << 1;
            a = sum;
        }
        return sum;
    }
}