Lintcode: A+B problem - neverlandly - 博客园

Lintcode: A+B problem - neverlandly - 博客园
For given numbers a and b in function aplusb, return the sum of them. Note You don't need to parse the input and output. Just calculate and return. Example If a=1 and b=2 return 3 Challenge Can you do it with out + operation?
考验Bit Operation, 可以用按位^异或两个操作数对应位以及carry，只是carry是1还是0需要分情况讨论。求更优的解法 复制代码 1 class Solution {

位运算实现整数加法本质就是用二进制进行运算。
其主要用了两个基本表达式：
x^y //执行加法，不考虑进位。
(x&y)<<1 //进位操作
令x=x^y ；y=(x&y)<<1 进行迭代，每迭代一次进位操作右面就多一位0，最多需要“加数二进制位长度”次迭代就没有进位了，此时x^y的值就是结果。

我们来做个3位数的加法：
101+011=1000 //正常加法
位运算加法：
（1） 101 ^ 011 = 110
(101 & 011)<<1 = 010
（2） 110 ^ 010 = 100
(110 & 010)<<1 = 100
（3） 100 ^ 100 = 000
(100 & 100)<<1 = 1000
此时进行相加操作就没有进位了，即000 ^ 1000=1000即是最后结果。

   public int aplusb(int a, int b) {
 8         while(b != 0){
 9             int carry = a & b;
10             a = a ^ b;
11             b = carry << 1;
12         }
13         return a;
14     }

   public int aplusb(int a, int b) {
2         // Click submit, you will get Accepted!
3         if (b == 0) return a;
4         int sum = a^b;
5         int carry = (a&b)<<1;
6         return aplusb(sum, carry);
7     }

Read full article from Lintcode: A+B problem - neverlandly - 博客园