29. Divide Two Integers

Tags

1. Math
2. Binary Search

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

题意：

在不使用乘法、除法和求余运算符的情况下划分两个整数。 如果是溢出，则返回MAX_INT。

分析：

在这个问题里面，我们不能用乘除法和求余数来处理两个整数的分解即相除，那我们能用什么来解决这个问题勒？答案显而易见就是位运算了。而javascript的位运算主要有以下几个：

1. ~ 按位非(NOT)
执行按位非操作的结果就是返回数值的反码。 本质即变成操作数的负值减1.
2. & 按位与(AND)
只有两个数值的对应位都是1时才返回1，任何一位是0，就返回0.
3. | 按位或(OR)
有一个位是1就返回1，只有两个位都是0的情况下才返回0.
4. ^ 按位异或(XOR)
两个数值对应位上只有一个1时才返回1，如果对应的两位都是1或者都是0，则返回0.
5. << 左移
将数值的所有位向左移动指定位数。左移不会影响操作数的符号位。相当于与2的幂次方相乘。
6. >> 有符号的右移
将数值的所有位向右移动指定位数，保留符号位。相当于除以2的幂次方。
7. >>> 无符号右移
对正数而言无符号和有符号右移结果相同。
对负数而言无符号右移操作会把负数的二进制码当做正数的二进制码来进行移动，而负数又是以补码表示的，所以操作后最终的结果会很大

根据以上知识点，可以知道本题我们可以使用<<左移和>>右移来替换*,\,%进行整数的分解相除。

思路：

主体思路是将除法转换为乘法进行分解。将被除数分解成除数与一个未知数相乘的计算。只要每次求解的结果不大于被除数即可，然后减去之后继续求解。将获得的未知数累加就可以得到最终的结果值。这里由于要用到位计算，所以这个未知数就是每次循环操作后位移数。

注

在具体实现过程中，一直会报超时错误，实验了很多次，在确信算法没问题的情况下，始终还是超时，于是在Discuss查了一下，发现一个使用js实现的描述：

The algorithm is just the same as many other posts, double the divisor by shifting left 1 bit.

But I still got TLE 3 times, the trick is: JavaScript bitwise op is for signed 32-bit, so

while ((base << 1) <= dividend) {
doesn't work. Because "base" overflows.

while (base <= (dividend >> 1)) {
works.

于是自己也做出修改后，就没有报超时错误了。

参考： https://discuss.leetcode.com/topic/39501/ac-javascript-code

复杂度

时间复杂度O(n²)

Js实现：

/**
 * @param {number} dividend
 * @param {number} divisor
 * @return {number}
 */

var divide = function(dividend, divisor) {
  const MAX_INT = 2147483647;
  const MIN_INT = -2147483648;

  // 将一些特殊情况进行特殊处理， 1、除数或被除数为0；2、被除数等于最小数以及除数等于-1；3.被除数和除数相等。
  if (dividend === 0 || divisor === 0) return 0;
  if (dividend === MIN_INT && divisor === -1) return MAX_INT;
  if(dividend === divisor) return 1;
  // 判断正负
  const isPositive = (dividend < 0) ^ (divisor < 0) ? false : true;
  //全部取正然后计算
  let dvs = Math.abs(divisor);
  let dvd = Math.abs(dividend);

  let res = 0;
  //如果被除数大于等于除数循环操作
  while (dvd >= dvs) {
    let count = 0;
    // 被除数向右位移count位，直到小于除数截至
    while (dvs <= dvd >> (count+1)) {
      count++;
    }
    //被除数减去位移后得数，记录本次计算的未知数的结果值
    res += 1 << count;
    dvd -= dvs << count;
  }
 // 重新赋值符号 
 if (!isPositive) res = -res;
 return res;

}

Discuss中的一种类似解法

/**
 * @param {number} dividend
 * @param {number} divisor
 * @return {number}
 */
var divide = function(dividend, divisor) {
  if (divisor === 0) return 0;
  if (dividend === 0) return 0;
  if (dividend === -2147483648 && divisor === -1) return 2147483647;

  var isPositive = true;
  if (dividend > 0 !== divisor > 0) isPositive = false;

  divisor = Math.abs(divisor);
  dividend = Math.abs(dividend);

  var count = 1,
    result = 0,
    base = divisor;

  while (dividend >= divisor) {
    count = 1;
    base = divisor;
    while (base <= (dividend >> 1)) {
      base = base << 1;
      count = count << 1;
    }
    result += count;
    dividend -= base;
  }

  if (!isPositive) result = -result;
  return result;
}