Skip to main content

两数相除

题目​

将两数相除, 不能用乘法/除法/取余等操作.

注意:

  • 被除数和除数均为 32 位有符号整数;
  • 除数不为 0;
  • 假设我们的环境只能存储 32 位有符号整数, 其数值范围是 [-2³¹, 2³¹ - 1]. 本题中, 如果除法结果溢出, 则返回 2³¹ - 1.
提示:
  • -2³¹ <= dividend, divisor <= 2³¹ - 1
  • divisor != 0
示例

输入: dividend = 7, divisor = 3

输出: 2

题解​

任何数字都等于 Math.pow(2, 0) + Math.pow(2, 1) + ... + Math.pow(2, i)

因此反过来: 商(r) * 除数(divisor) = 被除数(dividend)

所以 r 用 2 的次幂表示: (Math.pow(2, 0) + Math.pow(2, 1) + ... + Math.pow(2, i)) * divisor = dividend

所以该题就变成了求 i, 使 2 的次幂累加结果, 逼近 dividend.

/**
 * @param {number} dividend
 * @param {number} divisor
 * @return {number}
 */
var divide = function (dividend, divisor) {
  const INT_MAX = 2 ** 31 - 1
  const INT_MIN = (-2) ** 31
  const sign = (dividend < 0) ^ (divisor < 0) ? -1 : 1

  dividend = Math.abs(dividend)
  divisor = Math.abs(divisor)

  let ans = 0
  while (dividend >= divisor) {
    let temp = divisor,
      multiple = 1

    // a << 1 相当于 a * 2
    while (dividend >= temp << 1) {
      temp <<= 1
      multiple <<= 1
    }
    dividend -= temp
    ans += multiple
  }

  const res = ans * sign
  if (res < INT_MIN || res > INT_MAX) {
    return INT_MAX
  } else {
    return res
  }
}