题目：
给出两个整数a和b, 求他们的和, 但不能使用 + 等数学运算符。
如果 a=1 并且 b=2，返回3
你不需要从输入流读入数据，只需要根据aplusb的两个参数a和b，计算他们的和并返回就行。
显然你可以直接 return a + b，但是你是否可以挑战一下不这样做？
a和b都是 32位 整数么？
- 是的
我可以使用位运算符么？
- 当然可以
解题
上面提示了用位运算，通过不能够用加法，应该也会用到逻辑运算，感觉应该提取a、b的每位数据进行计算，也就是：a1 = a & 1 ，b1 = b & 1 这个就把a、b的最低位提取出来了，同时在进行下一位计算的时候a、b要右移一位，也就是 a = a>> 1 、b = b>> 1，下面问题是中间该怎么搞？参考博客。
a1、b1是a、b的对应位，carry1上一位的进位数，carry2是这一位的进位数，val是a1、b1、carry的和，计算结果有下表：
| a1 | b1 | carry1 | carry1 | val |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 1 | 0 |
| 0 | 1 | 1 | 1 | 0 |
下面即简单又不简单
val是第i位的数，carry2是要进位的数，下一轮循环将会代替carry1
val应该在第i位，左移i位可以解决问题，val = val << i
sum 用来保存结果，初始值是 0 ，sum和val进行或运算，<只要有一个1 就是1>，在进行地位运算的时候，高位都是0，也就是主要判断val的值是不是1的问题，sum = sum | val
这里的过程还真的不好想的
下一轮循环就是 a = a >> 1 b = b >> 1
Java程序：
class Solution { /* * param a: The first integer * param b: The second integer * return: The sum of a and b */ public int aplusb(int a, int b) { // write your code here, try to do it without arithmetic operators. int sum = 0 ; int carry = 0; for(int i = 0;i< 32 ;i++){ int a1 = a & 1; int b1 = b & 1; int val = 0 ; if(a1 == 0 && b1 == 0 && carry == 0){ val = 0; carry = 0; }else if(a1 == 1 && b1 == 1 && carry == 1){ val = 1; carry = 1; }else if(a1==0 && b1 ==0 || a1 ==0 && carry ==0 || b1 ==0 && carry ==0){ val = 1; carry = 0; }else{ val = 0; carry = 1; } val = val << i; sum = sum | val; a = a >> 1; b = b >> 1; } return sum; } };
总耗时: 660 ms
Python程序：
class Solution: """ @param a: The first integer @param b: The second integer @return: The sum of a and b """ def aplusb(self, a, b): # write your code here, try to do it without arithmetic operators. sum = 0 carry = 0 for i in range(32): a1 = a & 1 b1 = b & 1 val = 0 if a1== 0 and b1 ==0 and carry ==0: val =0 carry = 0 elif a1 == 1 and b1 == 1 and carry ==1: val =1 carry =1 elif a1 == 0 and b1 ==0 or a1==0 and carry ==0 or b1 ==0 and carry ==0: val = 1 carry = 0 else: val = 0 carry = 1 val = val << i sum = sum|val a = a>>1 b = b>>1 return sum
总耗时: 203 ms
这样写还是很好理解的，在上面的博客链接中，还有另外一种方法，比较不好理解。
异或运算^ 与运算 & 加法运算<考虑进位> 加法运算<不考虑进位>
0 ^ 0 = 0 0 & 0 = 0 0 + 0 = 0 0 + 0 = 0
1 ^ 0 = 1 1 & 0 = 0 1 + 0 = 1 1 + 0 = 1
1 ^ 1 = 0 1 & 1 = 1 1 + 1 = 10 1 + 1 = 0
0 ^ 1 = 1 0 & 1 = 0 0 + 1 = 1 0 + 1 = 1
可以看出加法不考虑进位的情况下和异或运算结果是一样的。
与运算结果是1时候，表示要进位 1.为了更好的计算，左移一位，这个就是要进位的，进位的在和上面的结果相加，出现了递归的现象了。
sum = a ^ b
carry= a&b
a = sum
b = carry
递归下去。。。 a b中有0的时候结束
OK
Java程序：
class Solution { /* * param a: The first integer * param b: The second integer * return: The sum of a and b */ public int aplusb(int a, int b) { // write your code here, try to do it without arithmetic operators. if(b==0) return a; return aplusb( a ^ b,(a&b)<<1); } };
总耗时: 586 ms
非递归程序：
class Solution { /* * param a: The first integer * param b: The second integer * return: The sum of a and b */ public int aplusb(int a, int b) { // write your code here, try to do it without arithmetic operators. if(b==0) return a; while(b!=0){ int sum = a ^ b; int carry = (a&b)<<1 ; a = sum; b = carry; } return a; } };
总耗时: 592 ms
上面中b后来被考虑成进位项，当所有位都没有进位时候也就是b ==0 的时候结束程序。
注意在递归程序中：不应该增加a==0的时候结束程序，可能出现a =0但是会进位的情况。
上面程序无论是递归还是非递归都是出现时间超时的问题。
class Solution: """ @param a: The first integer @param b: The second integer @return: The sum of a and b """ def aplusb(self, a, b): # write your code here, try to do it without arithmetic operators. if b == 0: return a if a == 0: return b while b!=0: carry = (a&b)<<1 a = a ^ b b = carry return a
都是这个数据的问题