【算法】用加减法实现整除法

来源

LeetCode 29. 两数相除，只保留整数部分 这道题由于加上了边界条件，导致需要进行一些逻辑判断，但是其实思路很简单, 下面解释一下核心思路。

最简实践

被除数 ➗ 除数，最简单的做法就是不断的 被除数 减去 除数，计算次数就能得到商。

实现如下

function div(a, b) {
  let count = 0;
  while (a >= b) {
    a -= b;
    count += 1;
  }
  return count;
}

进阶实现

既然 a 是 b 的倍数，那么我们可以胆子大点，不必每次减 b。可以尝试减去 b的倍数，如下。

function def(a, b) {
    let count = 1;
    // a 比 b小 没的除
    if (a < b) return 0;
    let tmpb = b;
    // 倍数相加判断 
    while (tmpb + tmpb <= a) {
      count += count;
      tmpb += tmpb;
    }
    // 减去倍数
    return count + def(a - tmpb, b);
  }