LCR 001. 两数相除

约 877 字大约 3 分钟

2026-03-10

题干

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

注意：

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

示例 1：

输入：a = 15, b = 2
输出：7
解释：15/2 = truncate(7.5) = 7

示例 2：

输入：a = 7, b = -3
输出：-2
解释：7/-3 = truncate(-2.33333..) = -2

示例 3：

输入：a = 0, b = 1
输出：0

示例 4：

输入：a = 1, b = 1
输出：1

提示:

-2^31 <= a, b <= 2^31 - 1
b != 0

思路

由于不能使用乘法和除法，考虑利用减法来进行计算。先考虑b的特殊取值。

在原数上进行快速相减可能会产生溢出，故考虑变换成负数进行计算。

在减法的思路上面，考虑移位运算快速确定商二进制表示的每一位。

代码

C++

class Solution {
public:
    int divide(int a, int b) {
        // 特殊情况1, b=1
        if (b == 1){
            return a;
        }
        // 特殊情况2, b=-1
        if (b == -1){
            // 判断是否溢出
            return a == Integer.MIN_VALUE ? Integer.MAX_VALUE : -a;
        }
        // 特殊情况3, a=0
        if (a == 0){
            return 0;
        }
        // 确定符号
        boolean positive = (a ^ b) >= 0;
        // 为避免溢出, 转换为负数进行计算
        a = a < 0 ? a : -a;
        b = b < 0 ? b : -b;
        // 快速相减
        int quotient = 0;
        while (a <= b){
            int base = 1;
            int divisor = b;
            // 使用减法, 避免溢出
            while (a - divisor <= divisor){
                divisor <<= 1;
                base <<= 1;
            }
            quotient += base;
            a -= divisor;
        }
        return positive ? quotient : -quotient;
    }
};

Python3

class Solution:
    def divide(self, a: int, b: int) -> int:
        if b == 1:
            return a
        if b == -1:
            return (1<<31) - 1 if a <= -(1<<31) else -a
        if a == 0:
            return 0
        positive: bool = (a ^ b) >= 0
        a = a if a < 0 else -a
        b = b if b < 0 else -b
        quotient: int = 0
        while a <= b:
            base: int = 1
            divisor: int = b
            while a - divisor <= divisor:
                divisor <<= 1
                base <<= 1
            quotient += base
            a -= divisor
        return quotient if positive else -quotient

JavaScript

/**
 * @param {number} a
 * @param {number} b
 * @return {number}
 */
let divide = function (a, b) {
  if (b == 1) {
    return a
  }
  if (b == -1) {
    return a <= -2147483648 ? 2147483647 : -a
  }
  if (a == 0) {
    return 0
  }
  let positive = (a ^ b) >= 0
  a = a > 0 ? -a : a
  b = b > 0 ? -b : b
  let quotient = 0
  while (a <= b) {
    let base = 1
    let divisor = b
    // 使用减法, 避免溢出
    while (a - divisor <= divisor) {
      divisor <<= 1
      base <<= 1
    }
    quotient += base
    a -= divisor
  }
  return positive ? quotient : -quotient
}

func divide(a int, b int) int {
	if b == 1 {
		return a
	}
	if b == -1 {
		if a <= -(1 << 31) {
			return (1 << 31) - 1
		} else {
			return -a
		}
	}
	if a == 0 {
		return 0
	}
	positive := (a ^ b) >= 0
	if a > 0 {
		a = -a
	}
	if b > 0 {
		b = -b
	}
	quotient := 0
	for a <= b {
		base := 1
		divisor := b
		for a-divisor <= divisor {
			divisor <<= 1
			base <<= 1
		}
		quotient += base
		a -= divisor
	}
	if positive {
		return quotient
	} else {
		return -quotient
	}
}

参考

两个数相除，可以通过反复减法来得到商，即用被除数不断减去除数，直到剩下的数小于除数，减的次数就是商。例如，计算20除以4，可以20-4=16，16-4=12，12-4=8，8-4=4，4-4=0，共减5次，所以商是5。
这种方法虽然直观，但效率较低，尤其是当除数较小或被除数较大时。为了快速计算，可以采用“倍数减法”的思路，即一次减去除数的若干倍，比如10倍、100倍等，这样能大大减少减法次数。这就是长除法的基本原理。在代码编写中，我们可以考虑这个倍数为2的幂次。

贡献者

Cuber-Wei