【算法】位运算算法——两整数之和

题解：两整数之和(位运算算法)

1.题目

题目链接：LINK

2.位运算算法

这个题目难点就在于不能用+、-

那什么能够代替加号呢？
既然数的层面不能用+号，那二进制的角度去用+号即可。

恰好，就有两个这种运算符恰好满足我们的需求。
按位异或，对不存在进位的数字进行相加。
按位与，对需要进位的数字取1

当我们对a^b进行异或的时候，
我们发现：
如果1和0不同的位数异或是我们想要的结果，但两个二进制都是1的时候进行异或就不对(红色代表不满足我们预期，绿色代表满足我们预期)

结论：错误的都是需要进位的二进制

那如何进行进位呢？
怎么确定哪几个二进制位需要进位？ ——按位与
按位与恰好可以解决我们这个问题，两个1的二进制位肯定是需要进位的啊(黄色代表需要进位的地方)。

那如何把这个黄色的位进到a^b上去呢？
我们可以把a&b向左移动一位，表示向其更高位进行进位。

然后我们再对a^b 和 (a&b)>>1再进行异或运算，看看能不能进上一位。

我们发现好像有个1进位成功，还一个没能成功，但是没关系，继续以此循环即可。

总过程如下：

3.参考代码

//一般版本
class Solution {
public:
    int getSum(int a, int b) 
    {
        int Carry = 1;
        while(Carry)
        {
           int add = a ^ b;
           Carry = (a & b) << 1;

           a = add;
           b = Carry;
        }

        return a;        
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

//语法优化
class Solution {
public:
    int getSum(int a, int b) 
    {
        do
        {
           a = a ^ b;
           b = (((a^b) & b) << 1);
        }while(b);

        return a;        
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

4.总结

我们本道题首先题目规定不能用+号，所以我们想到直接去二进制层面进行操作，用^代替无进位相加，用&代替进位，两者结合即可模拟出二进制层面加法的操作。

---

EOF