记录一下 LeetCode 做的一道题。要求实现两个整数的加法,但不能使用内置的+-. 原题地址:https://leetcode.com/problems/sum-of-two-integers/

我们来看一下答案:

1
2
3
4
5
6
class Solution {
public:
    int getSum(int a, int b) {
        return b == 0? a : getSum(a^b, (a&b)<<1);
    }
};

乍一看,似乎很难看,位运算毕竟不是很直观。重写一下,

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    int getSum(int a, int b) {
        int sum = a;
        while (b != 0) {
            sum = a^b; // sum w/o carry
            b = (a&b) << 1; // calculate the carry
            a = sum; // add this sum to next->a
        }
        return sum;
    }
}

or

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    int getSum(int a, int b) {
        int sum = a;
        if (b != 0) {
            sum = a^b;
            b = (a&b) << 1;
            return getSum(sum, b);
        }
        else {
            return sum;
        }
    }
}

除了将递归写成了迭代,其余部分都是照着第一段代码来的。重要的是为什么是这样?为什么会有

a + b == (a^b) + (a&b)<<1

现在我们挨个来看看a^ba&b到底是啥?首先a^b^是 C++ 中的按位异或运算符,它的运算表为:

  • 1^1 = 0
  • 0^0 = 0
  • 1^0 = 1
  • 0^1 = 1

现在我们把它竖过来看,或许你会发现一点东西:

       1011  <---+ a   X           1011
     ^ 1010  <---+ b   X         + 1010
a^b= -------           X    a+b= -------
       0001            X          10101

这好像就是二进制的加法呀?除了没有进位!那么进位在哪里呢?我们把目光转向a&b&是 C++ 按位与运算符,它的运算表如下:

  • 0&0 = 0
  • 0&1 = 0
  • 1&0 = 0
  • 1&1 = 1

可以看到,与运算只有一种情况为 1,这恰好对应着二进制加法中需要进位的情况。再加上进位需要向左边进一位,所以还应该左移一位加上之前的a^b,正好就是加法需要的结果。到这里你应该明白为什么a+b == (a^b) + (a&b)<<1.

接着,又有一个问题:随着程序的执行,b 为什么会变成 0?我们看看 b 是如何更新的,

1
2
3
sum = a^b;
b = (a&b) << 1; // b is updated
a = sum;

假设a&b = 1010 0111,那么 b 的值就会更新为:1010 0111 => 0100 1110,b 的最低位每次都会引入一个 0,而最高位被丢弃,这样的结果就是 b 中的 1 越来越少,0 越来越多,最终一定会变成 0. 而每次 b 中削减的值,全部间接通过 sum 被加到 a 中去了。如此以来,当 b 为 0 的时候,此时的 a 已经加到两者之和了。可以想象有两堆小球,每次迭代都将 b 这一堆的某些球挪到 a 中去,那么当 b 被挪完的时候,a 中就有了全部的小球。

还有一个问题,目前我还没有解决。上述答案贴到 LeetCode 里面是不通过的,因为接受的参数是 int 型的,可以为负,而将负数左移是未定义的行为。来日有时间再看看…

小结

位运算牛逼!无奈本人没文化,只能喊出这样的口号了。另外在做题的过程中,搜到了 CSDN 上的一篇文章,总结了很多位运算的技巧:here.

References

  1. 原题讨论帖
  2. 一人跟帖解释