两数相除

[louzhedong]

题目

出处：LeetCode 算法第29题

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

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

示例 1:

输入: dividend = 10, divisor = 3
输出: 3

示例 2:

输入: dividend = 7, divisor = -3
输出: -2

说明:

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

思路

由于不能使用乘法除法，我们可以使用减法来计算被除数包含几个除数，但当数值很大的时候直接循环做减法会花费很长的时间，所以可以使用位移运算符每次使除数加倍，让被除数减去位移后不超过被除数的最大除数，记录位移的次数。但即使这样使用JS也无法AC，寻求更好的解法。

解答

var divide = function (dividend, divisor) {
  var sign = ((dividend < 0) ^ (divisor < 0)) ? true : false;
  var divid = Math.abs(dividend);
  var divis = Math.abs(divisor);
  var result = 0;
  if (divid < divis) {
    return result;
  }
  while (divid >= divis) {
    var temp = divis, p = 1;
    while (divid >= (temp << 1)) {
      temp = temp << 1;
      p = p << 1;
    }
    divid -= temp;
    result += p;
  }

  return sign ? -result : result;
};

[ckaqq]

js 的位运算都是针对 32 位整数，所以 temp << 1 可能会溢出

加个溢出的判断 while (divid >= (temp << 1) && temp << 1 > temp) 和 边界判断可以 AC

完整代码：

var divide = function (dividend, divisor) {
  var sign = ((dividend < 0) ^ (divisor < 0)) ? true : false;
  var divid = Math.abs(dividend);
  var divis = Math.abs(divisor);
  var result = 0;
  if (divid < divis) {
    return result;
  }
  while (divid >= divis) {
    var temp = divis, p = 1;
    while (divid >= (temp << 1) && temp << 1 > temp) {
      temp = temp << 1;
      p = p << 1;
    }
    divid -= temp;
    result += p;
  }
  
  if (sign) {
    result = -result;
  }
  return Math.min(2147483647, Math.max(result, -2147483648));
};

[louzhedong]

@ckaqq 受教了