LeetCode 29. 两数相除:32 位整数下的位运算除法全解(doocs/leetcode 多语言实现)
LeetCode 29. 两数相除:32 位整数下的位运算除法全解(doocs/leetcode 多语言实现)
导读
LeetCode 29.「两数相除」要求在不使用乘法、除法和取余运算符的前提下完成 32 位有符号整数的除法,并严格约束溢出行为,是经典的「模拟 + 快速幂(二进制倍增)」题目。本篇文章以 doocs/leetcode 仓库中 0029.Divide Two Integers 题解为主体,系统讲解朴素减法的超时根因、负数域运算规避溢出的设计思想、二进制倍增的算法流程,并完整给出 Python3、Java、C++、Go、TypeScript、C#、PHP 七种语言的仓库实现。读完本文,你将掌握这类「禁止乘除 + 强约束溢出」题目的标准解题套路,并能直接对照仓库源码进行多语言验证与迁移。
题目描述与核心约束
给你两个整数,被除数 dividend 和除数 divisor。将两数相除,要求不使用乘法、除法和取余运算。整数除法应该向零截断(truncate),即截去其小数部分:
8.345截断为8-2.7335截断至-2
返回被除数 dividend 除以除数 divisor 得到的商。
注意:假设环境只能存储 32 位有符号整数,数值范围是 [−2^31, 2^31 − 1]。本题中,如果商严格大于 2^31 − 1,则返回 2^31 − 1;如果商严格小于 -2^31,则返回 -2^31。
示例 1:
输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = 3.33333..,向零截断后得到 3
示例 2:
输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = -2.33333..,向零截断后得到 -2
提示:
-2^31 <= dividend, divisor <= 2^31 - 1divisor != 0
思路分析:为什么朴素减法会超时
除法本质上就是减法。题目要求计算两数相除后的取整结果,本质上是计算:被除数由多少个除数、再加上一个小于除数的数构成。
最直观的做法是一次循环只做一次减法:只要被除数还能容纳一个除数,就从被除数中减去 1 × b,商加 1。但该做法的致命问题是:当 |a| 接近 2^31 时,需要循环约 2^31 次,必然超时,无法通过本题的时间限制。同时题目禁止使用乘法、除法与取余,因此必须另辟蹊径。
仓库题解给出的破局思路是快速幂(二进制倍增):
在剩余量仍够的前提下,将除数不断左移加倍,即可一次扣掉
2^k倍,商按二进制累加。这与快速幂的思想一致。左移时还需防止溢出:若再翻倍会超出 32 位范围,则停止倍增。
换句话说,与其一次减去 1 × b,不如尝试一次减去 2^k × b 这种尽可能大的块:把除数 b 通过左移不断翻倍,找到「翻倍后仍不超过剩余被除数」的最大块,一次性扣除并累加对应的商,然后对剩余部分重复该过程。这样每次外循环都能扣掉一大块,循环次数被压缩到对数级别。
难点解析:32 位溢出与负数域运算
题目明确要求环境只能存储 32 位有符号整数,因此必须格外小心溢出:
- 不能把负数转成正数再运算。例如当被除数为
INT32_MIN(即-2^31)时,转换为正数会得到2^31,大于INT32_MAX(2^31 - 1),直接溢出。 - 特判除数为 1:
b == 1时直接返回a,无需进入循环。 - 特判唯一溢出场景:当
a == -2^31且b == -1时,真实商为2^31,超出 32 位有符号整数上界,必须按题目要求返回2^31 - 1(即INT_MAX)。 - 符号单独记录:先用
(a > 0 && b > 0) || (a < 0 && b < 0)记录最终结果是否为正,然后把a、b统一转换为负数参与运算,全程在负数域上完成,从根源上规避取相反数导致的溢出。 - 左移防溢出:内层倍增循环中,必须确保
x在左移后仍处于 32 位有符号范围内。各语言使用不同的防溢出写法(详见下文实现),例如 Python 判断x >= -(2**30)、Java 判断x >= (Integer.MIN_VALUE >> 1),其共同语义是「x再翻倍不会越过-2^31下界」。
算法流程:二进制倍增逐块扣除
以负数域运算为例,核心流程如下:
- 特判
b == 1返回a;特判a == -2^31 && b == -1返回2^31 - 1。 - 记录符号
sign,将a、b统一转为负数。 - 初始化商
ans = 0。 - 外层循环
while a <= b(在负数域中,a <= b表示|a| >= |b|,即剩余被除数还能容纳除数):- 令
x = b、cnt = 1; - 内层循环不断执行
x <<= 1; cnt <<= 1,在满足「x翻倍不溢出」且「a <= (x << 1)」(翻倍后的块仍不超过剩余被除数)时继续倍增,找到当前能扣掉的最大块; - 执行
a -= x(扣掉这块),ans += cnt(商累加对应的2^k倍)。
- 令
- 根据
sign决定返回ans还是-ans。
该算法的时间复杂度为 O(log a × log b),空间复杂度为 O(1)。外层循环次数约为 O(log a),每次内层倍增的代价约为 O(log b)。
多语言实现(仓库完整源码)
以下实现均来自 doocs/leetcode 仓库 0029.Divide Two Integers 题解,并可在同目录的 Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.cs、Solution.php 中查看原文。
Python3
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
Java
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;
}
}
C++
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 >= -(1 << 30) && a <= x + x) {
x += x;
cnt <<= 1;
}
ans += cnt;
a -= x;
}
return sign ? ans : -ans;
}
};
Go
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
}
TypeScript
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;
}
C#
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;
}
}
PHP
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;
}
}
实现细节对比:各语言溢出防护写法
观察七种实现,可以归纳出两种防溢出策略:
| 语言 | 倍增防护条件 | 说明 |
|---|---|---|
| Python3 | x >= -(2**30) |
保证 x 再左移一位不会越过 -2^31 |
| Java | x >= (Integer.MIN_VALUE >> 1) |
Integer.MIN_VALUE >> 1 即 -2^30,与 Python 等价 |
| C++ | x >= -(1 << 30) |
同样的 -2^30 阈值,倍增用 x += x 代替左移 |
| Go | x >= (math.MinInt32 >> 1) |
math.MinInt32 >> 1 即 -2^30 |
| TypeScript | x >= -(2 ** 30) |
与 Python 写法一致 |
| C# | x >= (int.MinValue >> 1) |
与 Java 写法一致 |
| PHP | $a >= $x << 1(不额外防护) |
PHP 整数可自动扩容,直接用绝对值运算,天然规避 32 位溢出 |
可以看到,C/C++/Java/Go/C#/TypeScript 这些「整型严格受限」的语言都采用了 -2^30 阈值来约束倍增上限;而 PHP 因整数类型无 32 位截断问题,直接用 abs() 转为正数运算并省略防护条件,是唯一的例外实现。该对比可以帮你理解:溢出防护写法必须与目标语言的整数语义严格匹配。
复杂度与正确性小结
- 时间复杂度:
O(log a × log b)。外层循环每轮至少把被除数的规模缩小一半以上,内层倍增受 32 位范围约束最多约 31 次。 - 空间复杂度:
O(1),仅使用常数个变量。 - 正确性要点:
- 负数域运算保证了
a = -2^31这类极端输入不会因取相反数而溢出; - 特判
a == -2^31 && b == -1保证商溢出时按题目要求钳制到2^31 - 1; - 内层倍增循环保证每次扣掉的
x都是「不超过剩余被除数」的最大二进制块,商逐位按二进制累加,最终等价于向零截断的整数除法。
- 负数域运算保证了
仓库文件导航
- 中文题解:README.md
- 英文题解:README_EN.md
- 各语言源码:Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.cs、Solution.php
掌握「模拟 + 快速幂」的二进制倍增思想后,你还可以将其迁移到其他「禁止乘除 + 强溢出约束」的整数运算题目中;同类技巧在仓库的位运算与数学专题(可参考 solution/README.md 的题目索引)中反复出现,值得举一反三。