昨天在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.于是想到位运算，但是由于对位运算很不熟悉，于是上网搜了一下，得到如下表格：
| 含义 | Pascal语言 | C语言 | Java |
|---|---|---|---|
| 按位与 | a and b | a & b | a & b |
| 按位或 | a or b | a | b | a | b |
| 按位异或 | a xor b | a ^ b | a ^ b |
| 按位取反 | not a | ~a | ~a |
| 左移 | a shl b | a << b | a << b |
| 带符号右移 | a shr b | a >> b | a >> b |
| 无符号右移 | a>>> b |
好吧，其实一看都是一些布尔运算，也不难理解，接下来就是运算问题了。
举个例子试试看怎么算吧，比如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; }