思路

题目分析

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

• 方法一：非递归
  • 我们先通过非递归来理解算法流程
  • 两个数字相加的时候，我们先将两个数字视为二进制
  • 二进制与运算可以产生进位的方案，因此与运算后执行左移1位就是每轮需要进位的方案
  • 二进制或运算可以产生非进位的嘉加和结果，因此每轮都要加和一次两个数字，视是否有进位来决定是否要下一轮继续循环
• 方法二：递归
  • 我们可以以num2承接是否有进位的工作，num1作为加和的结果
  • 首先判断num2是否有进位

    • 如果有进位则递归调用函数，并将num1更新为或运算的结果，num2更新为与运算左移一位的结果

    • 如果无进位则返回num1，因为num1一直在记录加和结果

方法一：非递归

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

复杂度分析

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

方法二：递归

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

复杂度分析

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