让我们先用我们熟悉的加法对二进制数字进行推算；
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时，说明有进位。因此使用位运算实现整数的加法的步骤如下：
记
sum = a^b记
carry = (a&b) << 1-
若
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;
}
