[LintCode] 1 A + B Problem

Description

Write a function that add two numbers A and B. You should not use + or any arithmetic operators.

Example

Given a=1 and b=2 return 3

Note

There is no need to read data from standard input stream. Both parameters are given in function aplusb, you job is to calculate the sum and return it.

Challenge

Of course you can just return a + b to get accepted. But Can you challenge not do it like that?

Clarification

Are a and b both 32-bit integers?

• Yes.

Can I use bit operation?

• Sure you can.

思路
用二进制加法
在没有进位的情况下，两个二进制数相加结果等于两个数的异或。1101 + 0101不考虑进位就是1101 ^ 0101 = 1000。
考虑进位，用两个二进制数的与运算来判断。1101 + 0101的进位在1101 & 0101 = 0101。这表示有1的位置需要进位到左边进行下一次的加法。我们用<<左移的到结果(1101 & 0101) << 1 = 1010和上一次的相加结果1000进行相加，并产生新的进位。 循环相加，直到进位为0。这时的结果就是两个二进制数相加的结果。

1101 ^ 0101 = 1000
1101 & 0101 = 0101
0101 << 1 = 1010

1000 ^ 1010 = 0010
1000 & 1010 = 1000
1000 << 1 = 10000

0010 ^ 10000 = 10010
0010 & 10000 = 00000 stop

1101 + 0101 = 10010


Code

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.
        while (b != 0) {
            int carry = a & b;
            a = a ^ b;
            b = carry << 1;
        }
        
        return a;
    }
};

使用递归

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;
        }
        
        int carry = a & b;
        a = a ^ b;
        b = carry << 1;
        
        return aplusb(a, b);
    }
}