LintCode之A+B问题

A+B问题
描述:给出两个整数 aa 和 bb , 求他们的和。

算法思路

在十进制的加法中,例如 6+7,个位为3,十位为110,所以6+7 = 110 + 3 ,我们在二进制加法中也可以利用这种思想
即:先算每一位相加不进位,然后再算进位,进位需要乘以该位代表的倍数,在二进制里就相当是左移一位

重要工具:

• 利用抑或运算符计算出相加不进位的值 (抑或运算又称"不进位加法")

• 利用与运算符计算出进位的位置

• 利用左移运算符将其进位

  •  a ^ b 可求出二进制不进位加法得到的值
    

  •  a & b 可求出二进制加法需要进位的位置
    

  •  向前进一位 --- 将需要进位的位置左移一位
    

  •  将不进位加法得到的值与进的位相加 有可能又会引起进位
    

  •  重复上述步骤 --- 递归 直到没有进位 即b = 0 ,则a为最终结果
    

举例

 * 以3+5为例:
 *      3的二进制0011
 *      5的二进制0101
 *
 * 3^5 = 0110  6
 * 3&5 = 0001  1
 * 1 << 1 = 0010 2
 *
 * 则转换为6+2,重复上述步骤
 *      6的二进制0110
 *      2的二进制0001
 * 6^2 = 0111  8
 * 6&2 = 0000  0
 *
 * 进位为0,运算结束,结果为8

代码

    public static int getSum(int a, int b) {
        if(b == 0) {
            return a;
        }
        int c = a ^ b;
        b = (a & b) << 1;
        return getSum(c,b);
    }