关于算法:没有除法的除法LeetCode第29题

7 月初的时候挑战了一下 LeetCode 的第 29 题（中等难度，仿佛没什么值得炫耀的），题目要求在不应用除、乘，以及模运算的状况下，实现整数相除的函数。

既然被除数和除数都是整数，那么用减法就能够实现除除法了（如许 naive 的想法）。一个 trivial 的、用 JavaScript 编写的函数能够是上面这样的（为了简略起见，只思考两个参数皆为正整数的状况）

function divide(n, m) {
  let acc = 0;
  while (n >= m) {
    n -= m;
    acc += 1;
  }
  return acc;
}

如此奢侈的 divide 函数提交给 LeetCode 是不会被承受的的——它会在像 2147483648 除以 2 这样的测试用例上超时。能够在本地运行一下感触下到底有多慢

➜  nodejs time node divide.js
2147483648/2=1073741824
node divide.js  1.14s user 0.01s system 99% cpu 1.161 total

那么有没有更快的计算两个整数的商的算法呢？答案当然是必定的。

一眼就能够看出，运行次数最多的是其中的 while 循环。以 2147483648 除以 2 为例，while循环中的语句要被执行 1073741824 次。为了晋升运行速度，必须缩小循环的次数。

既然每次从 n 中减去 m 须要执行 n/m 次，那么如果改为每次从中减去 2m，不就只须要执行(n/m)/2 次了么？循环的次数一下子就缩小了一半，想想都感觉兴奋啊。每次减2m，并且自增 2 的算法的代码及其运行成果如下

➜  nodejs cat divide2.js
function divide(n, m) {
  let acc = 0;
  let m2 = m << 1; // 因为题目要求不能用乘法，所以用左移来代替乘以 2。while (n >= m2) {
    n -= m2;
    acc += 2;
  }
  while (n >= m) {
    n -= m;
    acc += 1;
  }
  return acc;
}

console.log(`2147483648/2=${divide(2147483648, 2)}`);
➜  nodejs time node divide2.js
2147483648/2=1073741824
node divide2.js  2.65s user 0.01s system 99% cpu 2.674 total

只管耗时不降反升，令局面一度非常难堪，但依据实践剖析可知，第一个循环的运行次数仅为原来的一半，而第二个循环的运行次数最多为 1 次，能够晓得这个优化的方向是没问题的。

如果计算 m2 的时候左移的次数为 2，那么 acc 的自增步长须要相应地调整为 4，第一个循环的次数将大幅降落至 268435456，第二个循环的次数不会超过 4；如果左移次数为 3，那么 acc 的步长增至 8，第一个循环的次数降至 134217728，第二个循环的次数不会超过 8。

显然，左移不能有限地进行上来，因为 m2 的值早晚会超过n。很容易算出左移次数的一个下限为

对数符号意味着即使对于很大的 n 和很小的m，上述公式的后果也不会很大，因而能够显著地晋升整数除法的计算效率。

在开始写代码前，让我先来简略地证实一下这个办法算进去的商与间接计算 n/m 是相等的。

记被减数为n，减数为m。显然，存在一个正整数N，使得

令

，再令

，那么 n 除以 m 等价于

证实结束。

从下面的公式还能够晓得，新算法将本来规模为 n 的问题转换为了一个规模为 r 的雷同问题，这意味着能够用递归的形式来优雅地编写最终的代码。

最终的 divide 函数的代码如下

function divide(n, m) {if (n < m) {return 0;}

  let n2 = n;
  let N = 0;
  // 用右移代替左移，防止溢出。while ((n2 >> 1) > m) {
    N += 1;
    n2 = n2 >> 1;
  }

  // `power` 示意公式中 2 的 N 次幂
  // `product` 代表 `power` 与被除数 `m` 的乘积
  let power = 1;
  let product = m;
  for (let i = 0; i < N; i++) {
    power = power << 1;
    product = product << 1;
  }
  return power + divide(n - product, m);
}

这个可比最开始的 divide 要快得多了，有图有假相

➜  nodejs time node divide3.js
2147483648/2=1073741824
node divide3.js  0.03s user 0.01s system 95% cpu 0.044 total

如果以 T(n, m) 示意被除数为 n，除数为m 时的算法工夫复杂度，那么它的递推公式能够写成下列的模式

但这玩意儿看起来并不能用主定理间接求出解析式，所以很遗憾，我也不晓得这个算法的工夫复杂度到底如何——只管我猜想就是 N 的计算公式。

如果有哪位善意的读者敌人晓得的话，还望不吝赐教。

浏览原文

关于算法:没有除法的除法LeetCode第29题

序言

尝试优化

一个简略的证实

残缺的代码

后记