不使用加法计算两个数的和

一、前置知识

为了能够快速的理解最后的算法，这里先准备一些前置知识。这些所谓的前置知识可以理解为“点”，最后只要把这些“点”串联为“线”，就会得到最终的答案。

1. a ^ b的含义

首先探索一下在二进制中a^b的结果，然后给这个结果加一个定义。

（1）穷举实例

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

根据异或运算的运算规则，对于某个二进制位上的两个数，如果这两个数同为0或者1那么异或的结果一定为0，否则异或的结果为1。
将异或运算和加法运算对比一下，得到如下的结果。

0 ^ 0 = 0 c 0 + 0 = 0
1 ^ 1 = 0 --------------------- 1 + 1 = 1 0
0 ^ 1 = 1 --------------------- 0 + 1 = 1
1 ^ 0 = 1 --------------------- 1 + 0 = 1

（2）结论

两个数a和b进行异或运算，在二进制角度，相当于对每对对应的bit位做了不进位的加法运算。

2. a & b的含义

（1）穷举实例

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

根于与运算的运算规则，对于某个二进制位上的两个数，如果这两个数都为1时得到的结果为1，否则得到的结果为0。
将与运算和加法运算对比一下，得到如下的结果。

0 & 0 = 0 --------------------- 0 + 0 = 0 进位值为0
0 & 1 = 0 --------------------- 0 + 1 = 1 进位值为0
1 & 0 = 0 --------------------- 1 + 0 = 1 进位值为0
1 & 1 = 1 --------------------- 1 + 1 = 1 0 进位值为1 、

（2）结论

两个数a和b进行异或运算，在二进制角度，相当于记录了每对对应的bit位进行加法运算以后所产生的进位。

（3）<< 位移

（2）中的结果将产生的进位记录在了运算的位置上，那么如果将整体左移1位，那么恰好就是把进位值移动到了应该被进到的位置上。

二、 连点成线

有了一种的前置知识以后，就可以按照如下的步骤来计算两个数的和了。这里设两个数为a 和 b。会得到如下的计算步骤。

• 把二进制的每一位都进行不进位的加法。
• 获取到每个bit位向上的进位值。
• 继续进行不进位的加法。
• 获取到每个bit位向上的进位值。
• 继续进行不进位的加法。
• …

三、代码

public int getSum(int a, int b) {
        while (b != 0) {
            int m = (a & b) << 1;
            a = a ^ b;
            b = m;
        }
        return a;
    }
1
2
3
4
5
6
7
8