算法自由之路

整数除法

题目

剑指 Offer II 001. 整数除法

给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' 。

注意：

  • 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8  以及 truncate(-2.7335) = -2
  • 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2^31, 2^31−1]。本题中，如果除法结果溢出，则返回 2^31 − 1

思路

除法不能用 *、/、% ？那该怎么办呢？将除数叠加以至等于被除数，或者被除数叠减以至于除数

如果存在两个数正负号不相同呢？考虑符号问题

考虑边界溢出问题，比如：-2^31 / -1 = 2^31 这个时候就要做边界处理

代码

1. 叠减法

/**
 * @param {number} a
 * @param {number} b
 * @return {number}
 */
var divide = function (a, b) {
  // 考虑数值溢出问题
  const MAX = Math.pow(2, 31) - 1;
  const MIN = -Math.pow(2, 31);
  if (a == MIN && b == -1) {
    return MAX;
  }
  if (a == MIN && b == 1) {
    return MIN;
  }

  // 异或运算直接判断符号是否相同
  const isNegative = (a > 0) ^ (b > 0);

  a = Math.abs(a);
  b = Math.abs(b);

  let time = 0;

  // 不断叠减以至于除数小于被除数
  while (a >= b) {
    a -= b;
    time++;
  }

  return isNegative ? -time : time;
};

2. 位运算

/**
 * @param {number} a
 * @param {number} b
 * @return {number}
 */
var divide = function (a, b) {
  const MAX = Math.pow(2, 31) - 1;
  const MIN = -Math.pow(2, 31);
  if (a == MIN && b == -1) {
    return MAX;
  }
  if (a == MIN && b == 1) {
    return MIN;
  }
  const negative = (a > 0) ^ (b > 0);
  a = Math.abs(a);
  b = Math.abs(b);
  let time = 0;

  // 这段位运算无法理解
  for (let x = 31; x >= 0; x--) {
    if ((a >>> x) - b >= 0) {
      a = a - (b << x);
      time = time + (1 << x);
    }
  }
  return negative ? -time : time;
};