不用加减乘除做加法

写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。

思路：

考虑使用位运算，对于整数a和整数b，求a+b，在位层面进行的话，每一位有四种情况：
0+0=0
1+0=1
0+1=1
1+1=10
前三种情况不需要进位，第四种情况需要进位，并且相加的位变为0。可以把位相加拆为两步：第一步不进位的相加a^b，第二步由第一步的结果加上需要进位的情况,进位的情况就是a&b<<1。而第二步的操作是另一个a+b，所以是递归的过程。终止条件就是(a&b<<1)==0

代码一：

class Solution {
public:
    int add(int a, int b) {
        if(b == 0) {
            return a;
        }
        return add(a^b,(a&b) << 1);
    }
};

代码二：

class Solution {
public:
    int add(int a, int b) {
        while (b != 0) {
            int carry = (a & b) << 1;
            a = a ^ b;
            b = carry;
        }
        return a;
    }
};