lintcode算法题 1. A + B 问题
描述给出两个整数 a 和 b , 求他们的和。你不需要从输入流读入数据，只需要根据aplusb的两个参数a和b，计算他们的和并返回就行。
说明 a和b都是 32位 整数么？ 是的。我可以使用位运算符么？ 当然可以
样例 如果 a=1 并且 b=2，返回3。
挑战 显然你可以直接 return a + b，但是你是否可以挑战一下不这样做？（不使用++等算数运算符）
代码：Talk is cheap. Show me the code.
int add(int a,int b){
if(b==0){
return a;
}else{
return add(a^b,(a&b)<<1);
}
}
分析：
这道题用到的是位运算，位运算符中与加有关的首先想到的是异或运算。
1. 异或：相异为1，相同为0。
特殊情况下，异或运算的结果与+相同。比如5和2
5+2 = 0101 + 0010 = 0111 = 7
5^2 = 0101 ^ 0010 = 0111 = 7
结果都是7。在5和2的二进制加法中刚好不存在进位，如果存在进位那又是什么情况呢。比如6和2
6+2 = 0110 + 0010 =1000 = 8
6^2 = 0110 ^ 0010 = 0010 = 2
可见，当需要进位的时候结果就不相同了。所以不需要进位的我们可以用异或，需要进位的我们继续分析。
2. 左移：把所有二进制位左移n位，右边补0（这里不考虑有符号无符号和溢出的问题）。
对于二进制进位，首选左移。左移一位相当于给所有是1的位进位一次，比如
3 << 1 = 0011 << 1 = 0110 = 6
回归我们的问题，进位有了，剩下的我们要找出哪些位需要进位，也就是那些位在两个加数里都是1，这里就又需要一个新的位运算 与
3. 与：都是1为1，否则为0。
在我们的问题中，与运算后为1的位需要进位。即a&b的结果需要进位，进位用左移，即(a&b)<<1 可以计算出进位后的结果。
整个计算过程是这样的
1. 先异或（a^b）： 筛选不能进位的二进制位 标记为1 计算出中间数b1。
2. 然后与（a&b）： 筛选需要进位的二进制位 标记为1 ；再左移（(a&b)<<1） 理解为 进位 对需要进位的二进制位进位 计算出中间数a1。
3.注意：此时的 a1+b1 == a+b。把a1看作a，把b1看作b，继续1，2步骤，直到b==0，也就是没有需要进位的二进制位。此时的a就是原来的a+b的结果。
例子：
a = 15 , b = 22 求 a+b
-------------------------------
第一轮运算
a = 15 0000 1111 a原值
b = 22 0001 0110 b原值
a^b = 25 0001 1001 筛选出的不需要进位的位，计作a1
a&b = 6 0000 0110 筛选出的需要进位的位
a&b<<1 = 12 0000 1100 给需要进位的位 进位，结果计作b1
-------------------------------
第二轮运算
a = 25 0001 1001 第一轮计算出的a1
b = 12 0000 1100 第一轮计算出的b1
a^b = 21 0001 0101
a&b = 8 0000 1000
a&b<<1 = 16 0001 0000
-------------------------------
第三轮运算
a = 21 0001 0101
b = 16 0001 0000
a^b = 5 0000 0101
a&b = 16 0001 0000
a&b<<1 = 32 0010 0000
-------------------------------
第四轮运算
a = 5 0000 0101
b = 32 0010 0000
a^b = 37 0010 0101
a&b = 0 0000 0000
a&b<<1 = 0 0000 0000
-------------------------------
第五轮运算，此时b==0，a即运算结果。
a = 37 0010 0101
b = 0 0000 0000
-------------------------------
结果
a+b = 37
-------------------------------
最后
初学者 参考了网上很多资料搞明白的，感谢各位乐于分享的大神，希望可以给以后同学一点帮助。如有错误，欢迎指正。
网友评论