不使用加法计算两数之和

2021-07-13

举例两个数字的位图

1 2	3 //0011 1 //0001

当相加时，每个位上都可能发生四种种情况：

两个数对应的位都是 0，相加后仍然为 0。
两个数对应的位一个是 1，另一个是 0，相加后为 1。
两个数对应的位都是 1，相加后产生进位，结果为 0
两个数对应的位一个是 1，另一个是 0。相加后为 1，然后接收到了下一位相加产生的进位 1，最终结果为 0，并且产生了一个进位 1。

$\begin{array}{cc|c} A&B&F\\ \hline 0&0&0\\ 0&1&1\\ 1&0&1\\ 1&1&0\\ \end{array}$

若不考虑进位，只针对每一位来看，这就是一个异或操作。

相加

所以先不考虑进位，进行一次异或操作，得到的就是这两个数相加之后，每一个位不考虑进位的结果：

3 //0011
1 //0001

3 ^ 1 //0010

进位

那么进位的情况怎么计算呢？

很简单，两个数对应的位都是 1 的时候，在相加之后这一位就会产生进位。

也就是两个数进行与操作，结果中为 1 的位将会发生进位。

例如在这个例子中，相加之后会产生进位的位置应该是：

1
2
3

3 //0011
1 //0001
3 & 1 //0001

而进位的结果是当前位变 0 ，1 进到下一位上，也就是：

显然这是一个左移操作。

求和

现在只需要把这两部分整合到一起就可以加法结果。

但此时得到的两部分结果，相加之后同样可能发生进位。这里就需要先进行进位判断，也就是将两部分进行与操作，并判断结果是否为 0：

当结果为 0 时就说明不会发生进位了
否则就继续对这两部分进行上述的相加和进位操作，得到对应的两部分结果，然后继续判断是否发生进位。

最后在不会发生进位时，将这两部分结果进行异或操作，就得到了这两个数字的和。

0010 & 0010        //0010 != 0 还会发生进位

0010 ^ 0010        //0000 求不考虑进位相加后的结果
(0010 & 0010) << 1 //0100 求相加后产生的进位结果
0000 & 0100        //0000 没有进位了
0000 ^ 0100        //0100 最终结果

经上述分析，将加法操作分成了三部分：

两数异或，得到不考虑进位的结果。
两数与，得到只考虑进位后的结果。
第 1 步和第 2 步中得到两部分结果进行与。若会发生进位就对这两部分结果重复执行第 1 步和第 2 步；直到不会发生进位时，对这两部分求异或得到最终结果。

golang代码实现

func add(a int, b int) int {
  xor := a ^ b
  and := (a & b) << 1
  for (xor & and) != 0 {
    tmp := xor
    xor ^= and
    and = (tmp & and) << 1
  }
  return xor ^ and
}