LeetCode笔记：371. Sum of Two Integers
LeetCode笔记：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.
大意：
计算a和b两个整数的和，但是不能用+或-运算符。 比如： 给出 a = 1 和 b = 2，返回 3.
思路：
这道题乍看之下很简单，计算两个数之和嘛，但问题在于不能直接使用加号和减号，这就尴尬了，不过如果不这样，也称不上一道题了。其实对于运算，我们知道计算机本身就是没有什么加减乘除的，一切都是二进制在进行一些位运算，所以这里很显然的一个思路也就是转换成位运算，当然如果你本来就知道加法的实现原理，那也可以直接拿来做了。
我们先看个位数的二进制运算： 1 + 1 = 10； 1 + 0 = 1； 0 + 1 = 1； 0 + 0 = 0。
如果我们用^，也就是位异或运算来做： 1 ^ 1 = 0； 1 ^ 0 = 1； 0 ^ 1 = 1； 0 ^ 0 = 0。
其实观察可以看到，异或和直接的加唯一结果有区别的就是1+1这一条，但是换个想法，1+1是要进位的，进位后个位上还是变成0了，这样就一样了，只不过还需要有一个进位操作，而对于二进制，只有都是1的时候才会进位，这立马就可以联想到“与”操作了对不对： 1 & 1 = 1； 1 & 0 = 0； 0 & 1 = 0； 0 & 0 = 0。
既然是进位，我们当然要将得出来的结果进一位，这里使用左移运算符就可以了，所以对于1+1这种的做法就是异或加上与的进位： 1+1 = 1^1 + (1&1)<<1
当然我们还是不能有加号，所以对上那个加法我们还是要使用同样的方法，这就是递归了，那要到什么时候为止呢，从逻辑上来说，到不再有进位就可以了。
现在我们看一个二位数的加法：11+ 10 = 101
首先11^10 = 01， 然后11&10 = 10，左移一位得100， 现在有进位，那么继续 01+100， 01^100 = 101， 01&100 = 000， 这时候与操作后的结果为0了，可以停止运算了，最后的的结果应该是101，答案正确。说明思路是对的。
代码（Java）
public class Solution {
public int getSum(int a, int b) {
if (b == 0) return a;
int sum,up;
sum = a^b;
up = (a&b)<<1;
return getSum(sum, up);
}
}代码很简单，递归调用，在每次调用中都先检查进位的计算是不是为0了，也就是是不是没有进位了，如果没有了说明异或运算就是最终结果了，如果还有进位就继续算下去，算异或和与之后的左移然后继续调用。
看来这些看似理所当然的最简单的运算符，内里的门道也是需要了解清楚的。