不用加减乘除做加法

题目链接

• 牛客网

题目描述

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

数据范围：两个数都满足−10≤n≤1000

进阶：空间复杂度O(1)，时间复杂度O(1)

刷题思路

方案一： 利用自增

方案二： 利用位运算

1 + 1 = 0      1 ^ 1 = 0  ##错误
1 + 0 = 1     1 ^ 0 = 1  ##正确
0 + 1 = 1     0 ^ 1 = 1  ##正确
0 + 0 = 0      0 ^ 0 = 0  ##正确

1 & 1 = 1  ##进位
1 & 0 = 0  ##不进位
0 & 1 = 0  ##不进位
0 & 0 = 0  ##不进位

• 当前位的和值等于 A(i)^B(i)
• 进位等于 A(i)&B(i),进位需要加在计算位的前一位，所以左移1位，即A(i)&B(i)<<1

所以找出规律 A+B=A^B+(A&B)<<1

即：函数的第一个参数接受不进位的操作结果，第二个参数接受进位操作的结果

代码实现

/**
 * 【简单】不用加减乘除做加法
 * - 利用自增
 * @param num1
 * @param num2
 */
function addOne(num1, num2) {
  // 整数递增
  if (num2 > 0) {
    while (num2 > 0) {
      num2--
      num1++
    }
  }

  // 负数递减
  if (num2 < 0) {
    while (num2 < 0) {
      num2++
      num1--
    }
  }
  return num1
}

/**
 * 【简单】不用加减乘除做加法
 * - 利用位运算【递归】
 * @param num1
 * @param num2
 */
function addTwo(num1, num2) {
  return num2 ? addTwo(num1 ^ num2, (num1 & num2) << 1) : num1
}

/**
 * 【简单】不用加减乘除做加法
 * - 利用位运算【循环】
 * @param num1
 * @param num2
 * @returns {number}
 */
function addThree(num1, num2) {
  let result = 0
  let carry = 0
  do {
    // 不带进位的加法
    result = num1 ^ num2
    // 进位
    carry = (num1 & num2) << 1
    num1 = result
    num2 = carry
  } while (carry !== 0) // 进位不为0则继续执行加法处理进位
  return result
}

console.log(addOne(1, 2))
console.log(addTwo(3, 4))
console.log(addThree(3, 4))

一些建议

• 注意ES6中位运算，左移<< ,右移>>
• 循环的写法