不用加减乘除做加法|算法专题

# 题目

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

# 思路

将加法拆解成三步：

• 1.不进位相加
• 2.计算进位
• 3.进位与不进位结果进行相加
• 重复这三步，直到进位值为0

举一个十进制的例子 5 + 17：

• 1.不进位相加 -> 12
• 2.计算进位 -> 5+7 产生进位 10
• 3.进位与不进位结果进行相加 12 + 10 = 22

使用二进制代替上面的过程：

• 5 的二进制为101，17的二进制为10001
• 1.不进位相加 -> 101+10001=10100
• 2.计算进位 -> 10
• 3.进位与不进位结果进行相加 10100 + 10 = 10110，转换成十进制后即22

使用位运算来计算二进制：

• 二进制异或操作和不进位相加得到的结果相同(1^1=0 0^1=1 0^0=0)
• 二进制与操作后左移和进位结果相同（1&1=1 1&0=0 0&0=0）

# 代码

递归实现

    function Add(num1, num2) {
      if (num2 === 0) {
        return num1;
      }
      return Add(num1 ^ num2, (num1 & num2) << 1);
    }

非递归实现

    function Add(num1, num2) {
      while (num2 != 0) {
        const excl = num1 ^ num2;
        const carry = (num1 & num2) << 1;
        num1 = excl;
        num2 = carry;
      }
      return num1;
    }

# 考察点

• 位运算
• 二进制