两整数之和

无意间在leetcode发现了这个有意思的题目，这个题目让我们写一个函数，这个函数接收两个整数作为参数，在不使用加法的情况下返回其相加的结果。不使用加法返回加法结果，这看上去很奇怪，在现实世界上可能，但是在计算机的二进制世界是可以做到的。

分析

首先我们想一想在10进制中我们是如何做加法的，比如说123 + 321，这两个数相加的结果是444，随便从幼儿园找个小朋友也知道，我们只需要按照对应位置相加就可以得到结果了，可是每一位只能放0-9这10个数，超过9就得进位，所以我们来看下面这两个数是怎么相加的，456+645,这两个数相加的结果是1101，我们拆分一下加法的过程，把按位相加的结果和进位的结果分开，在个位上6+5=11，由于不需要进位，个位上保留的结果就是1，再来看10位，5+4=9，所以十位上保留的结果就是9，再来看百位，4+6=10，保留百位上的数值，所以就是0，现在我们就得到了没有进位的结果，这个结果是091，再来分析一下只有进位的结果，由于没有比个位小的位，所以就没有人给个位进位，所以个位的进位就是0，再来看看10位，由于个位相加的结果是11所以十位上进位的结果就是1，再来看看百位，由于十位上相加的结果是9，所以百位上面也没有进位，再来看看千位上的结果，由于百位上相加的结果是10，所以千位上面的进位结果为1，最终我们得到了只有进位的结果，这个结果为1010，我们把没有进位的结果加上只有进位的结果，最终得到的结果是1101，这和直接相加的结果一样。

异或运算

上面我们分析了加法的过程，所以只要找到两种种运算，其运算结果为无进位的结果，和只有进位的结果，最终重复此运算，直到没有进位不久时我们所得的结果了吗？，在二进制中还真就有这么一种位运算其结果和二进制无进位相加的结果一摸一样，我们知道异或的结果如果两个数相同那么异或的结果就是0，反之就是1，在二进制中就两个数，所以只有一个数为1另一个数为0时结果才为1，而这正好和加法一样0+1也等于1，1+1=10，由于不要进位，所以其结果也是0，这太巧了。

与运算

上面介绍了异或运算的结果刚好和无进位加法的结果一摸一样，所以我们现在只需要找到另一种运算，其结果只等于进位加法，在位运算中刚好也有这么一种运算，就是我们经常使用的按位与，在二进制中只有都为1才需要进位，所以1+1的结果为10，但是1&1的结果却是1，这不符合预期啊，别急，我们仔细思考一下，进位的结果应该是要放到高位上去的，所以我们把它左移一位，这时候得到的结果就正好是10，我们再来试一个大点的数以11（3）+ 101(5)为例，11&101=001，左移一位，结果刚好是10，这与只有进位的加法一摸一样。

代码

var getSum = function(a, b) {
  while (b != 0) { // 进位结果为0，无需再计算了直接退出循环
      const carry = (a & b) << 1; // 得到只有进位的结果
      a = a ^ b; // 得到无进位的结果
      b = carry; // 重复计算无进位结果和只有进位结果，直到进位结果为0
  }
  return a;
};

递归版本

var getSum = function(a, b) {
    if(b===0) return a // 如果进位结果为0就结束递归
    const carry = (a & b) << 1;
    const c = a ^ b;
    return getSum(c, carry)
};

总结

别看代码这么短，如果不懂原理这个题目根本就写不出来，越底层的东西越值得大家去深思，但是知道并且理解其原理之后，这个题目就简单的和1+1一样，如果上面的文字描述没有看懂，可以看一下我手绘的过程 不使用加法运算实现两数相加