题目：给出两个整数 a 和 b , 求他们的和。

说明:a和b都是32位整数
题目一看很简单，只要 return a+b;即可。
但是直接return a+b 的效率并不高，效率只超过27%的人，边尝试其他方法，后面发现大家有使用位运算来进行操作。
但是一直对位运算不是很了解，于是便趁这个机会研究一下位运算。
我们知道计算机在进行加减运算时是使用补码进行运算的，那么在这里，我们来回顾一下二进制原码，补码，反码的知识。
注：因为题目a和b都是32位整数，所以一下均为在32位整数下的介绍，关于位操作的详细介绍参考：https://blog.csdn.net/briblue/article/details/70296326
那么，我们开始吧！

原码 反码 补码

原码：将一个数转换成二进制就是它的原码。（正数的符号位为，负数的符号位为1）

//以正数8和负数5为列
 8 = 0000 0000 0000 1000
-5 = 1000 0000 0000 0101

反码：正数的反码和原码一样，而负数的补码就是在原码的基础上，符号位不变，其他位置0变为1,1变为0。

//以正数8和负数5为列
 8  = 0000 0000 0000 1000
-5  = 1111 1111 1111 1010

补码：正数的补码还和原码一样，负数的补码是在原码的基础上加1。

//以正数8和负数5为列
 8 = 0000 0000 0000 1000
-5 = 1111 1111 1111 1011

那么我们上边提到过，计算机在进行运算时，本质就是二进制补码的运算

//那么8+（-5）的本质就是：
0000 0000 0000 1000 
1111 1111 1111 1011
相加得到的结果是
(1) 0000 0000 0000 0011
我们发现最前边多了一个1，因为进位问题这个1超过了16位，就被舍弃了，那么得到的结果就是
0000 0000 0000 0011 = 3
正好等于结果3（即8-5）

下边就要介绍一些常见的位运算符(&，|，^,>>,<<)

&与运算符

&运算符的计算规则是：只有当两个数都为1时，结果才为1，否则结果为0。

//以正数3和正数5为例(s即3&5)
3= 0000 0000 0000 0011
5= 0000 0000 0000 0101
s= 0000 0000 0000 0001 = 1
我们得到的结果为1（记住这个结果，后面我们会用到这个信息）
//以负数-3和正数5为例(s即-3&5)
-3 = 1111 1111 1111 1101
 5 = 0000 0000 0000 0101
 s = 0000 0000 0000 0101 = 5
我们得到的结果是5（不用过多的去纠结5和-3+5的结果2的关系，如果你迫不及待的话，可以跳过|或运算符直接去看^异或运算符）

|或运算符

|运算符的计算规则是：只要参与运算的有一个1，结果就为1，如果都为0，则结果为0。

//以正数3和正数5为例(s即3|5)
3= 0000 0000 0000 0011
5= 0000 0000 0000 0101
s= 0000 0000 0000 0111 = 7
我们得到的结果为7
//以负数-3和正数5为例(s即-3|5)
-3 = 1111 1111 1111 1101
 5 = 0000 0000 0000 0111
 s = 1111 1111 1111 1111 = 65535
我们的得到的结果是65535

^ 异或运算符

^运算符的计算规则是：只有当两个数不同时，才为1 。

//以正数3和正数5为例(s即3^5)
3= 0000 0000 0000 0011
5= 0000 0000 0000 0101
s= 0000 0000 0000 0110 = 6
我们得到的结果是6
这个时候我们先回想一下3+5的二进制运算过程
3= 0000 0000 0000 0011
5= 0000 0000 0000 0101
s= 0000 0000 0000 1000 = 8
如果上边为什么等于8不理解的话请看下边关于二进制加法的规则：
二进制运算时，从末位向前看，0+0=1,1+0=1,1+1= 10（即向前进一位，类似与10进制满十进1，二进制为满2进1）
好了，现在我们回到正题:怎么使用位运算来实现上述加法
（1）我们先来回顾一下3&5的过程
//以正数3和正数5为例(s即3&5)
3= 0000 0000 0000 0011
5= 0000 0000 0000 1001
s= 0000 0000 0000 0001 = 1
我们会发现，3&5的结果就是我们需要进位的那个值，只有为1+1时，我们才需要进位，而&运算保留的就是1+1位置的值
（2）我们在来看一下刚说过的^运算符
//以正数3和正数5为例(s即3^5)
3= 0000 0000 0000 0011
5= 0000 0000 0000 0101
s= 0000 0000 0000 0110 = 6
我们发现，^运算符保留的是一个位加法中一个为0，一个为1位数的值，这正是不需要进位的值，我们结合&和^运算符，是不是和二进制加法
的过程有点相似？
没错！&运算的结果是加法时需要进位的值，而^保留的是加法时不需要进位的值，而二进制的本质就是进位的值*2加上不进位值的结果，那么就是
&运算的结果*2+^运算的结果就是二进制运算的本质，我们来验证一下 ^运算的结果6+&运算的结果1*2结果正是我们要的8，即3+5；

看到这里，问题就迎刃而解，我们只要把a+b换成a^b+2*(a&b)即可，但是又出现新的问题，乘法的本质也是数个加法，我们这样反而把问题变得更加复杂，那么怎么解决乘法的问题呢，我们下边来介绍位移运算符。

<< 左移运算符

<<运算符的计算规则为：将数字整体向左移动一位，符号位不变，低位补0,<<后面跟数字几则为移动几位

//我们以3和5为例
3 = 0000 0000 0000 0011
3<<1 = 0000 0000 0000 0110 = 6
5 = 0000 0000 0000 0101
5<<1 = 0000 0000 0000 1010 = 10
我们发现3和5在位移一位后都变成原来的2倍，这是因为2进制是以2为单位（可以参考10进制，10进制左移一位，整体数值变大为原来的10倍）。
那么我们刚才乘2的问题就解决了，我们只需要将a^b+2*(a&b)更改为a^b+(a&b)<<即可。

现在问题从a+b变为了a^b+(a&b)<<,我们会发现a&b在位移后与前面的相加，仍是一个二进制加法，所以还是要使用刚才的方法，没错，这里就要使用递归，直到有一个数为0是，结束递归，那么我们直接来看代码吧。

public class Solution {
    /**
     * @param a: An integer
     * @param b: An integer
     * @return: The sum of a and b 
     */
    public int aplusb(int a, int b) {
        // write your code here
        if(a == 0)
            return b;
        if(b == 0)
            return a;
        int sum = (a&b)<<1;
         return aplusb(sum,a^b);
    }
}

以下为位运算的结果，我们可以看到效率的确是变高了。

位运算的结果

以下为直接return a+b的结果

不使用位运算