通过位运算求两个数的和(求解leetcode:371. Sum of Two Integers)

昨天在leetcode做题的时候做到了371，原题是这样的：

371. Sum of Two Integers

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

Example:
Given a = 1 and b = 2, return 3.

因为之前完全没有在实际练习中使用过位运算，所以刚看到这道题目的时候我的第一反应是

1.用乘除代替加减，但是一想，觉得恐怕不行，因为乘除本质上也是加减法，不可能跳过加减法做运算。

2.然后又想到或许可以转成二进制再用逻辑运算计算？但是问题是转成二进制不难，但是转回来还是得用加减法呀！看来这种方法也不行。

3.于是想到位运算，但是由于对位运算很不熟悉，于是上网搜了一下，得到如下表格：

好吧，其实一看都是一些布尔运算，也不难理解，接下来就是运算问题了。

举个例子试试看怎么算吧，比如3 + 1，该怎么算呢？由于位运算都是基于二进制的也就是3 + 1 = （011） + （001），如果列竖式计算的话就是

    0 1 1

+   0 0 1

-----------

    0 1 0

+   0 1 0

-----------

    1 0 0

看懂了吗？其实就是模拟进位：

1.首先最低位相加是要进一的

2.然后在做第二位的运算

3.以此类推，一直到没有进位为止。

那么必须弄清楚什么时候需要进位，很明显，当同一位上的数字都是1的时候需要进位，进位以后下一位变成1，也就是3 & 1中等于1的地方是需要进位的，然后左一一位，使下一位变成1， 然后下一位需要加的数字就是 3 ^ 1。

C++代码实现如下：

int getSum(int a, int b) {
    while(a != 0) {
        int tmp = (a & b) << 1;
        b = a ^ b;
        a = tmp;
    }
    return b;
}