# 题目

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

# 思路

将加法拆解成三步:

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

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

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

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

  • 5的二进制为10117的二进制为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;
    }

# 考察点

  • 位运算
  • 二进制