位运算实现整数加法

让我们先用我们熟悉的加法对二进制数字进行推算；

101 + 011 = 1000

如果忽略进位，那么在计算每一位时推算如下：

1 + 1 = 0

1 + 0 = 1

0 + 0 = 0

这样让我们想到了位运算的按位异或运算，那既然如此简单就赶紧用按位异或试试上面的例子：101 ^ 011 = 110, 这结果和正确答案相差甚远啊！！

别急，那是因为我们在按位异或时，忽略了进位。既然存在进位的情况，我们就看看什么情况下会进位呢？不难发现，当两个要进行相加的数存在对应的位都为1时才会进位，那么我们要怎么知道对应的两个位都为1呢？ 与运算！

现在我们知道了异或执行加法，与运算会获得进位。

获得进位使用 (a&b) << 1.

执行加法使用a^b

当(a&b)<<1的结果不为0时，说明有进位。因此使用位运算实现整数的加法的步骤如下：

1. 记sum = a^b

2. 记carry = (a&b) << 1

3. 若carry != 0, a = sum; b = carry 。 重复1，2步骤；

   若carry == 0，sum即为所求结果。

上面步骤中，为什么当carry != 0时，需要重复步骤1，2？ 这是考虑当两个数相加时出现连续进位的情况。我们不妨看看连续进位和不连续进位这两种情况：

• 不连续进位：

  例子1010 + 1010:

  1010 ^ 1010 = 0000

  (1010&1010) << 1 = 10100(carry)

  0000 ^ 10100 = 10100(sum)

  在此例子中， carry不为0的情况下，我们没有继续循环计算，但是结果却是正确的。

• 连续进位

  例子011 + 001, 看的出结果为100，下面进行不重复1，2步骤和重复步骤1，2进行计算：

  • 不重复步骤1，2：

    011 ^ 001 = 010

    (011&001) << 1 = 010 (carry)

    010 ^ 010 = 0(sum)

  • 重复步骤1，2：

    First Loop:

    ​ 011 ^ 001 = 010

    ​ (011&001) << 1 = 010 (carry) (不为0)

    Second Loop：

    ​ 010 ^ 010 = 0

    ​ (010&010) << 1 = 100(carry) (不为0)

    Third Loop:

    ​ 0 ^ 100 = 100

    ​ (0&100) << 1 = 0 (carry) (为0)

    计算正确。

代码实现：

//迭代版本
int Add(int a, int b) {
    int sum = a^b;
    int carry = (a&b) << 1;
    while (carry) {
        int s = a^b;
        int c = (a&b) << 1;
        sum = s;
        carry = c;
    }
    return sum;
}

//递归版本
int Add(int a, int b) {
    return b? Add(a^b, (a&b)<<1) : a;
}