A+B问题

问题描述:给出两个整数a和b,求他们的和, 但不能使用+等数学运算符。

说明

a和b都是 32位 整数么?

  • 是的

我可以使用位运算符么?

  • 当然可以

样例

如果 a=1 并且 b=2,返回3

 

思路:很明显,题目提示了我们应该用去位运算就做这道题。这里主要用到异或运算和与运算,在Java中分别为^和&

先来看看异或运算:

1^1=0
1^0=1
0^1=1
0^0=0

和加法运算对比:

1+1=10
1+0=1
0+1=1
0+0=0

可以看出异或运算与不进位的加法结果一致,而加法产生进位的那一位我们可以通过与运算得出。

举个栗子:

a=110,b=10
a+b=1000
a^b=100
a&b=010
//进位左移一位就是100了,1000=100+100
a+b = a^b + (a&b)<<1

于是用递归可以做这道题:

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

done.