整数除法不使用/或*运算符

Question

我正在阅读算法和数据结构教科书,并提出了这个问题:

1-28.编写一个函数来执行整数除法而不使用/或*运算符.找到一种快速的方法来做到这一点.

我们怎样才能想出一个快速的方法呢？

Answer 1

我喜欢这个解决方案:https:|//stackoverflow.com/a/34506599/1008519 ,但我发现它有点难以推理(特别是-part).这个解决方案让我的头脑更有意义:

var divide = function (dividend, divisor) {
  // Handle 0 divisor
  if (divisor === 0) {
    return NaN;
  }

  // Handle negative numbers
  var isNegative = false;
  if (dividend < 0) {
    // Change sign
    dividend = ~dividend+1;
    isNegative = !isNegative;
  }

  if (divisor < 0) {
    // Change sign
    divisor = ~divisor+1;
    isNegative = !isNegative;
  }

  /**
   * Main algorithm
   */

  var result = 1;
  var denominator = divisor;
  // Double denominator value with bitwise shift until bigger than dividend
  while (dividend > denominator) {
    denominator <<= 1;
    result <<= 1;
  }

  // Subtract divisor value until denominator is smaller than dividend
  while (denominator > dividend) {
    denominator -= divisor;
    result -= 1;
  }

  // If one of dividend or divisor was negative, change sign of result
  if (isNegative) {
    result = ~result+1;
  }

  return result;
}

1. 我们将结果初始化为1(因为我们要将分母加倍,直到它大于股息)
2. 将我们的分母(按位移)加倍,直到它大于被除数
3. 既然我们知道我们的分母比我们的股息更大,我们可以减去我们的除数,直到它低于我们的股息
4. 返回结果,因为分母现在使用除数尽可能接近结果

以下是一些测试运行:

console.log(divide(-16, 3)); // -5
console.log(divide(16, 3)); // 5
console.log(divide(16, 33)); // 0
console.log(divide(16, 0)); // NaN
console.log(divide(384, 15)); // 25

以下是解决方案的要点:https://gist.github.com/mlunoe/e34f14cff4d5c57dd90a5626266c4130