Question

29. 两数相除

English Version

题目描述

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

整数除法应该向零截断，也就是截去（truncate）其小数部分。例如，8.345 将被截断为 8 ，-2.7335 将被截断至 -2 。

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

注意：假设我们的环境只能存储 32 位 有符号整数，其数值范围是 [−231,  231 − 1] 。本题中，如果商 严格大于 231 − 1 ，则返回 231 − 1 ；如果商 严格小于 -231 ，则返回 -231 。

 

示例 1:

输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = 3.33333.. ，向零截断后得到 3 。

示例 2:

输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = -2.33333.. ，向零截断后得到 -2 。

 

提示：

• -231 <= dividend, divisor <= 231 - 1
• divisor != 0

解法

方法一：模拟 + 快速幂

除法本质上就是减法，题目要求我们计算出两个数相除之后的取整结果，其实就是计算被除数是多少个除数加上一个小于除数的数构成的。但是一次循环只能做一次减法，效率太低会导致超时，可借助快速幂的思想进行优化。

需要注意的是，由于题目明确要求最大只能使用 32 位有符号整数，所以需要将除数和被除数同时转换为负数进行计算。因为转换正数可能会导致溢出，如当被除数为 INT32_MIN 时，转换为正数时会大于 INT32_MAX。

假设被除数为 $a$，除数为 $b$，则时间复杂度为 $O(\log a \times \log b)$，空间复杂度 $O(1)$。

class Solution:
  def divide(self, a: int, b: int) -> int:
    if b == 1:
      return a
    if a == -(2**31) and b == -1:
      return 2**31 - 1
    sign = (a > 0 and b > 0) or (a < 0 and b < 0)
    a = -a if a > 0 else a
    b = -b if b > 0 else b
    ans = 0
    while a <= b:
      x = b
      cnt = 1
      while x >= (-(2**30)) and a <= (x << 1):
        x <<= 1
        cnt <<= 1
      a -= x
      ans += cnt
    return ans if sign else -ans

class Solution {
  public int divide(int a, int b) {
    if (b == 1) {
      return a;
    }
    if (a == Integer.MIN_VALUE && b == -1) {
      return Integer.MAX_VALUE;
    }
    boolean sign = (a > 0 && b > 0) || (a < 0 && b < 0);
    a = a > 0 ? -a : a;
    b = b > 0 ? -b : b;
    int ans = 0;
    while (a <= b) {
      int x = b;
      int cnt = 1;
      while (x >= (Integer.MIN_VALUE >> 1) && a <= (x << 1)) {
        x <<= 1;
        cnt <<= 1;
      }
      ans += cnt;
      a -= x;
    }
    return sign ? ans : -ans;
  }
}

class Solution {
public:
  int divide(int a, int b) {
    if (b == 1) {
      return a;
    }
    if (a == INT_MIN && b == -1) {
      return INT_MAX;
    }
    bool sign = (a > 0 && b > 0) || (a < 0 && b < 0);
    a = a > 0 ? -a : a;
    b = b > 0 ? -b : b;
    int ans = 0;
    while (a <= b) {
      int x = b;
      int cnt = 1;
      while (x >= (INT_MIN >> 1) && a <= (x << 1)) {
        x <<= 1;
        cnt <<= 1;
      }
      ans += cnt;
      a -= x;
    }
    return sign ? ans : -ans;
  }
};

func divide(a int, b int) int {
  if b == 1 {
    return a
  }
  if a == math.MinInt32 && b == -1 {
    return math.MaxInt32
  }

  sign := (a > 0 && b > 0) || (a < 0 && b < 0)
  if a > 0 {
    a = -a
  }
  if b > 0 {
    b = -b
  }
  ans := 0

  for a <= b {
    x := b
    cnt := 1
    for x >= (math.MinInt32>>1) && a <= (x<<1) {
      x <<= 1
      cnt <<= 1
    }
    ans += cnt
    a -= x
  }

  if sign {
    return ans
  }
  return -ans
}

function divide(a: number, b: number): number {
  if (b === 1) {
    return a;
  }
  if (a === -(2 ** 31) && b === -1) {
    return 2 ** 31 - 1;
  }

  const sign: boolean = (a > 0 && b > 0) || (a < 0 && b < 0);
  a = a > 0 ? -a : a;
  b = b > 0 ? -b : b;
  let ans: number = 0;

  while (a <= b) {
    let x: number = b;
    let cnt: number = 1;

    while (x >= -(2 ** 30) && a <= x << 1) {
      x <<= 1;
      cnt <<= 1;
    }

    ans += cnt;
    a -= x;
  }

  return sign ? ans : -ans;
}

public class Solution {
  public int Divide(int a, int b) {
    if (b == 1) {
      return a;
    }
    if (a == int.MinValue && b == -1) {
      return int.MaxValue;
    }
    bool sign = (a > 0 && b > 0) || (a < 0 && b < 0);
    a = a > 0 ? -a : a;
    b = b > 0 ? -b : b;
    int ans = 0;
    while (a <= b) {
      int x = b;
      int cnt = 1;
      while (x >= (int.MinValue >> 1) && a <= (x << 1)) {
        x <<= 1;
        cnt <<= 1;
      }
      ans += cnt;
      a -= x;
    }
    return sign ? ans : -ans;
  }
}

class Solution {
  /**
   * @param integer $a
   * @param integer $b
   * @return integer
   */

  function divide($a, $b) {
    if ($b == 0) {
      throw new Exception('Can not divide by 0');
    } elseif ($a == 0) {
      return 0;
    }
    if ($a == -2147483648 && $b == -1) {
      return 2147483647;
    }
    $sign = $a < 0 != $b < 0;

    $a = abs($a);
    $b = abs($b);
    $ans = 0;
    while ($a >= $b) {
      $x = $b;
      $cnt = 1;
      while ($a >= $x << 1) {
        $x <<= 1;
        $cnt <<= 1;
      }
      $a -= $x;
      $ans += $cnt;
    }

    return $sign ? -$ans : $ans;
  }
}