不用加号实现加法

题目说明

这是一道在lintcode上的简单题：http://lintcode.com/en/problem/a-b-problem/

说明如下：
Write a function that add two numbers A and B. You should not use + or any arithmetic operators.
翻译过来就是在不使用算数操作符（加减乘除）的前提下实现加法函数。

解题思路

如果对二进制运算有所了解的话，那这道题就是一道很简单的题目。
禁止使用加减乘除，就是告诉我们需要通过二进制的逻辑运算来实现。

在二进制中的加法有如下规律：
0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 10
其中1 + 1比较特殊，结果为10，需要进位。如果暂时先不考虑进位，那么1 + 1当前位结果为0，也就是说：
0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 0
这个结果是不是很熟悉？对的，这就是异或操作的结果。所以对于同位，我们可以使用异或操作来进行计算：int xor = a ^ b;

接下来我们再考虑进位。二进制中，只有在两个数都为1时，才会产生进位，所以这里需要用逻辑与操作。而进位本身这个动作我们可以用左移来实现：int conj = (a & b) << 1;

这两步完成之后，我们需要对不进位结果和进位结果进行同样的操作，直到进位为0为止。所以在函数的最后我们需要递归调用aplusb，最终才能得到正确的结果。

代码实现

C++

int aplusb(int a, int b) {
    // write your code here
    if (b == 0) {
        return a;
    }
    
    int xor = a ^ b;
    int conj = (a & b) << 1;
    
    return aplusb(xor, conj);
}

题目延伸

实现了加法，那该如何实现减法呢？
其实很简单，我们知道减法也可以写成加法的形式：a - b = a + (-b)
这样一想的话，实现减法的核心就是得到b对应的负数-b。在二进制中，我们可以通过取反加一这个操作来得到一个数的负数。

代码也很简单，可以直接使用上面的aplusb函数：

int aminusb(int a, int b) {
    // write your code here
    return aplusb(a, aplusb(~b, 1));
}