不使用加法运算符求和

题目

不使用加法运算符，求两数之和，原题链接http://www.lintcode.com/zh-cn/problem/a-b-problem/

分析

不允许使用加法运算符，也就是不允许使用四则运算符，否则可以转换为减法， a + b == a - (-b) 。禁用四则运算符后，就只能依赖位运算了。

单靠位运算能进行四则运算么？当然可以！CPU中的重要部件算术逻辑单元ALU就是通过位运算实现的数学计算。只要能实现加法，四则运算就都可以实现，因为四则运算最终可以归结加法运算，减法是加法的逆运算，乘法就是加法的，除法是乘法的逆运算。

位运算加法

先考虑最简单的加法情况，即不包含进位，这里讲的进位是二进制状态下的进位，比如二进制数100+010=110这种情况。

    100
+   010
--------
    110

可以发现，如果没有任何进位的情况下，两个二进制数相加，只有1+0和0+0两种情况，1+0=>1，0+0=>0，这恰好与位运算异或（XOR）的运算规则一致！此时 A + B = A XOR B

如果两个二进制数相加，有进位的话又回如何呢？假设两个二进制数分别为1010和1111

    1010
+   1111
---------
   10001

会产生进位的地方，只有同等位上的值同时为1，显然，通过逻辑与运算，就可以得知产生进位的二进制位。

1010

&   1111

1010

再完整的回顾一下，位运算相加的过程：

• 先不考虑进位，A XOR B获得无进位的运算结果
• 通过A AND B计算出进位的值
• 如果有进位，将进位部分左移一位（向高位进位）
• A+B的问题，此时变成了 (A OXR B) + (A & B)的问题，迭代计算