不用加减乘除做加法

题目的主要信息：

• 题目给出两个数字
• 我们需要给出两个数字相加的结果
• 题目要求我们不可以用加减乘除符号
• 因此与或非运算就是我们可以用的方式

举一反三：

学习完本题的思路你可以解决如下题目：

JZ15. 二进制中1的个数

JZ56. 数组中只出现一次的两个数字

JZ64. 求1+2+3+...+n

方法一：位运算非递归（推荐使用）

知识点：位运算

计算机的数字由二进制表示，我们平常的运算是对整个数字进行运算，但是还可以按照二进制的每一位分别进行运算。常见运算有位与、位或、移位、位异或等。

思路：

由于题目禁止我们使用+，-，*，/运算符，我们需要通过位运算来实现加法。我们需要通过循环迭代两个变量实现，一个变量指代进位，一个变量指代非进位。

位运算中两数进行异或运算可以提供两数加和后二进制非进位信息，位运算中的两数进行与运算的结果可以提供两数加和后的二进制进位信息。因此我们将两数与运算的结果进行循环左移一位，并在下一轮循环中继续将移位后的进位结果和非进位结果求和，重复此过程，直到不再产生进位为止。

具体做法：

• step 1：两数进行与运算可以产生进位的信息
• step 2：运算后执行左移1位就是每轮需要进位的方案
• step 3：两数进行异或运算可以产生非进位的加和结果
• step 4：将移位后的进位结果与非进位结果继续重复 step 1 - step 3 的步骤，直到不再产生进位为止

图示：

Java实现代码：

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

C++实现代码：

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

Python实现代码：

class Solution:
    def Add(self , num1: int, num2: int) -> int:
        # add表示进位值
        add = num2
        # sum表示总和
        sum = num1
        # 当不再有进位的时候终止循环
        while add:
            # 将每轮的无进位和与进位值做异或求和
            temp = sum ^ add
            # 进位值是用与运算产生的
            add = (sum & add) << 1
            # 更新sum为新的和(处理负数问题)
            sum = temp & 0xFFFFFFFF 
        return sum if sum >> 31 == 0 else sum - 4294967296

复杂度分析：

• 时间复杂度：$O(log(max(num1,num2)))O(log(max(num1,\; num2)))$，因为考虑二进制之后其实在原数字的基础上求了对数，循环的次数也和二进制位数相关
• 空间复杂度：$O(1)O(1)$，没有额外引入空间

方法二：位运算递归（扩展思路）

知识点：位运算

计算机的数字由二进制表示，我们平常的运算是对整个数字进行运算，但是还可以按照二进制的每一位分别进行运算。常见运算有位与、位或、移位、位异或等。

思路：

由于题目禁止我们使用+，-，*，/运算符，我们需要通过位运算来实现加法。我们需要通过循环迭代两个变量实现，一个变量指代进位，一个变量指代非进位。

位运算中两数进行异或运算可以提供两数加和后二进制非进位信息，位运算中的两数进行与运算的结果可以提供两数加和后的二进制进位信息。因此我们将两数与运算的结果进行循环左移一位，并在下一轮循环中继续将移位后的进位结果和非进位结果求和，重复此过程，直到不再产生进位为止。

在递归中我们让num2承载进位信息，让num1承载加和信息，进行递归。

具体做法：

• step 1：以num2承接是否有进位的工作，num1作为加和的结果
• step 2：首先判断num2是否有进位
• step 3：如果有进位则递归调用函数，并将num1更新为或运算的结果，num2更新为与运算左移一位的结果
• step 4：如果无进位则返回num1，因为num1一直在记录加和结果

Java实现代码：

public class Solution {
    public int Add(int num1,int num2) {
        // 递归地求和，也是判断是否有进位值，此时进位值用num2来表示，每轮的结果都存储在num1中
        return num2 != 0 ? Add(num1 ^ num2, (num1 & num2) << 1) : num1;
    }
}

C++实现代码：

class Solution {
public:
    int Add(int num1, int num2) {
        // 递归地求和，也是判断是否有进位值，此时进位值用num2来表示，每轮的结果都存储在num1中
        return num2 ? Add(num1 ^ num2, (num1 & num2) << 1) : num1;
    }
};

Python实现代码：

class Solution:
    def Add(self , num1: int, num2: int) -> int:
        # 处理负数情况（递归最深的时候）
        if num1 >> 31 != 0 and num2 == 0:
            num1 -= 4294967296
        # 递归
        return num1 if num2 == 0 else self.Add((num1 ^ num2) & 0xFFFFFFFF, (num1 & num2) << 1)

复杂度分析：

• 时间复杂度：$O(log(max(num1,num2)))O(log(max(num1,\; num2)))$，因为考虑二进制之后其实在原数字的基础上求了对数，循环的次数也和二进制位数相关
• 空间复杂度：$O(log(max(num1,num2)))O(log(max(num1,\; num2)))$，递归栈的深度