剑指offer(C++)-JZ65：不用加减乘除做加法(算法-位运算)

作者：翟天保Steven
版权声明：著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处

题目描述：

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

数据范围：两个数都满足−10≤n≤1000
进阶：空间复杂度O(1)，时间复杂度O(1)

示例：

输入：

1,2

返回值：

3

解题思路：

本题考察位运算。两种解题思路。

1）位运算-非递归

       加法中，对同一位而言，如果都是0则为0，如果有一个1一个0则为1，如果有两个1，则当前位0且有进位1；异或运算^可得到两个数的非进位，与运算&后左移1可得到两个数的进位；非进位和进位再进行一次异或运算和与运算，如果没有出现进位，那就相当于两者完成了相加；若出现了新的进位，则重复上述操作直到进位消失。

2）位运算-递归

       递归运算相当于把while循环以递归形式执行，原理是一致的。

测试代码：

1）位运算-非递归

class Solution {
public:
    int Add(int num1, int num2) {
        // add表示进位值
        int add = num2;         
        // sum表示总和       
        int sum = num1;                
        // 当不再有进位的时候终止循环
        while(add != 0) {              
            // 将每轮的无进位和与进位做异或运算
            int temp = sum ^ add;      
            // 进位通过用与运算左移1产生的
            add = (sum & add) << 1;    
            // 更新
            sum = temp;                
        }
        return sum;
    }
};

2）位运算-递归

class Solution {
public:
    int Add(int num1, int num2) {
        // 递归地求和
        return num2 ? Add(num1 ^ num2, (num1 & num2) << 1) : num1;
    }
};