给出两个整数a和b, 求他们的和, 但不能使用 + 等数学运算符。

说明

a和b都是 32位 整数么？

  • 是的

我可以使用位运算符么？

  • 当然可以

异或相当于的加法，实现加法器的时候就是用很多个异或。

  1. 当前位相加，当前位的结果：

    0 + 0 = 0

    0 + 1 = 1

    1 + 0 = 1

    1 + 1 = 0

    很明显这和我们异或的结果的一样的。

  2. 两数相加，有可能进位。我们知道，二进制的加法，同位数相加的时候，要进位，就得两个数都是1。这其实和并(&)的计算是一样的。

    a&b的结果：

    0 & 0 = 0

    0 & 1 = 0

    1 & 0 = 0

    1 & 1 = 1

    a&b的结果中，第n位数为1，表示的是2个数的第n位相加，需要进位。相当于在第n+1位上面+1.相当于需要把a&b的结果往左移动1个二进制位。也就是a&b<<1；

所以 a+b 应该等于 a^b + (a&b)<<1 的结果。

但是 a^b +(a&b)<<1之后有可能还会进位，所以我们还需要用递归的方法来继续计算，直到没有进位为止。