题目：
给出两个整数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
都是这个数据的问题