给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

被除数和除数均为 32 位有符号整数。
除数不为 0。
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2^31, 2^31 − 1]。本题中，如果除法结果溢出，则返回 2^31 − 1。

思路

  1. 不让用乘除法和 mod 运算的情况下可使用位运算，将被除数右移，与除数进行比较，多次计算累加进而得出结果
  2. 统一转化成正数进行处理，被除数为 −2^31、除数为 −2^31、-1、1 时需要特殊处理
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
var divide = function (dividend, divisor) {
  const MAX_VAL = (1 << 30) - 1 + (1 << 30)
  const MIN_VAL = -1 << 31
  if (dividend === MIN_VAL) {
    if (divisor === -1) {
      return MAX_VAL
    } else if (divisor === 1) {
      return MIN_VAL
    } else if (divisor === MIN_VAL) {
      return 1
    }
  }
  const isNegative = (dividend < 0) ^ (divisor < 0)
  dividend = Math.abs(dividend)
  divisor = Math.abs(divisor)
  let result = 0
  while (dividend >= divisor) {
    let bit = 0
    while (divisor <= dividend >> (bit + 1)) {
      ++bit
    }
    result += 1 << bit
    dividend -= divisor << bit
  }
  return isNegative ? -result : result
}

优化

  1. KMP 算法，时间复杂度 O(m + n)