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 - 1b != 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 -quotientJavaScript
/**
* @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
}Go
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的幂次。
