a+b位运算

题目描述

A + B 问题

给出两个整数 a 和 b , 求他们的和。

样例

样例 1:

　输入: a = 1, b = 2

　输出: 3

　样例解释:

　　返回a+b的结果.

样例 2:

　输入: a = -1, b = 1

　输出: 0

　样例解释:

　　返回a+b的结果.

挑战

　显然你可以直接 return a + b，但是你是否可以挑战一下不这样做？（不使用++等算数运算符）

说明

1. a和b都是 32位 整数么？ 是的

2. 我可以使用位运算符么？ 当然可以

   注意事项

   你不需要从输入流读入数据，只需要根据aplusb的两个参数a和b，计算他们的和并返回就行。

分析

不考虑进位的加法是a,b的异或运算（0 ^ 0=0，1 ^ 0 =1，0 ^ 1=1，1 ^ 1=0）

只考虑进位的加法是a,b的&运算（0&0=0，0&1=0，1&0=0，1&1=1）

那么a+b的值则是a ^ b + (a&b)<<1

考虑到只能使用位运算，可以递归直到a&b的值为0，此时a的值就是两者之和。

C++代码如下

class Solution {
public:
    /**
     * @param a: An integer
     * @param b: An integer
     * @return: The sum of a and b 
     */
    int aplusb(int a, int b) {
        int s=0,c=0;
        s=a^b;
        c=(a&b)<<1;
        if(c!=0)
            s=aplusb(s,c);
        return s;
    }
};