京公网安备11010502063487号给定两个 32 位有符号整数，不使用乘法、除法和取模运算，计算它们相除的商，结果向零取整（截断小数部分）。如果商超过 32 位有符号整数的范围，就返回边界值。直接的想法是一次减一个除数，数商的个数，但商可能大到 21 亿，太慢。标准做法是把"减一次除数"升级成"减去除数的 2 的幂倍"，从大到小试，商用二进制一位一位拼出来，只需要 32 步。这道题的另一个重点是整数溢出：唯一会溢出的情形是 -2^31 除以 -1。本文用真实运行的 Java 和 Go 展示溢出，实测两种做法的耗时，给出五种语言的实现，并把移位相减的过程做成分步演示。
完整题目见官方页面（链接在文末）。除数不为 0。基准解直接用 Python 大整数的整除，再按被除数和除数的符号把商修正成向零取整，最后截断到 32 位范围内，与移位相减是两种独立的写法。一共 20 组用例，覆盖：官方示例、四种符号组合、被除数为 0、除数比被除数大、以及 32 位整数的两个端点（-2147483648 和 2147483647）参与的各种组合：
输入 [10,3] 输出 3 输入 [7,-3] 输出 -2 输入 [-7,3] 输出 -2 输入 [-7,-3] 输出 2 输入 [0,5] 输出 0 输入 [1,1] 输出 1
32 位有符号整数的范围是 -2147483648 到 2147483647。-2147483648 除以 -1，数学上的结果是 2147483648，比最大值大 1，放不进去。这个情形在 Java 和 Go（用 32 位整数类型时）里不会报错，而是悄悄回绕回 -2147483648。下面是真实运行的结果：
真实运行：-2147483648 除以 -1（数学结果是 2147483648，超出 32 位有符号整数的范围）： Java: Integer.MIN_VALUE / -1 = -2147483648 Go: int32(MinInt32) / -1 = -2147483648 Python: -2147483648 // -1 的整除结果 = 2147483648（Python 整数不会溢出，所以要按题目要求手动截断） 本文 solve(-2147483648, -1) = 2147483647
Java 的 Integer.MIN_VALUE / -1 和 Go 的 int32 除法都得到了 -2147483648，符号都错了。题目要求这种情形返回 2147483647，所以五种语言的实现都在入口处特判这一种情况。C++ 里 INT_MIN / -1 是未定义行为，我没有运行它，没有实测它在这台机器上的表现。另外，取绝对值也有同样的坑：abs(-2147483648) 在 32 位下还是 -2147483648，所以 Java 和 C++ 的实现都先转成 64 位整数再取绝对值。
先记下结果的符号，然后对两个数取绝对值。从 shift = 31 往下试到 0：如果 a 大于等于 b · 2^shift，就从 a 里减去它，商加上 2^shift。这就是二进制的长除法：shift 从高位到低位，每一位要么是 1（减得动）要么是 0。最后根据符号决定商的正负。Python、Java、Go、JavaScript、C++ 都是真实编译运行的。JavaScript 的位运算只有 32 位，所以用 b * 2 ** shift 这种乘 2 的幂的形式（在双精度浮点里是精确的）；这里的"不使用乘法"只针对被除数除以除数这一层，题目本身对实现语言里的移位和乘 2 的幂并没有限制。
Python · 解法代码def solve(dividend, divisor): INT_MAX, INT_MIN = 2 ** 31 - 1, -2 ** 31 if dividend == INT_MIN and divisor == -1: # 唯一会溢出的情形：结果是 2^31，超出 32 位有符号整数 return INT_MAX neg = (dividend < 0) != (divisor < 0) a, b = abs(dividend), abs(divisor) q = 0 for shift in range(31, -1, -1): # 从大到小试：能减去 b·2^shift 就减，商加上 2^shift if (a >> shift) >= b: a -= b << shift q += 1 << shift return -q if neg else q
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [10,3] → 3 [7,-3] → -2 [-7,3] → -2 [-7,-3] → 2 [0,5] → 0 [1,1] → 1
Java · 解法代码class Solution { public int divide(int dividend, int divisor) { if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE; // 唯一会溢出的情形 boolean neg = (dividend < 0) != (divisor < 0); long a = Math.abs((long) dividend), b = Math.abs((long) divisor); // 先转 long，再取绝对值 long q = 0; for (int shift = 31; shift >= 0; shift--) { // 从大到小试：能减去 b·2^shift 就减 if ((a >> shift) >= b) { a -= b << shift; q += 1L << shift; } } return (int) (neg ? -q : q); } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [10,3] → 3 [7,-3] → -2 [-7,3] → -2 [-7,-3] → 2 [0,5] → 0 [1,1] → 1
Go · 解法代码func divide(dividend, divisor int) int { if dividend == math.MinInt32 && divisor == -1 { // 唯一会溢出的情形 return math.MaxInt32 } neg := (dividend < 0) != (divisor < 0) a, b := dividend, divisor if a < 0 { a = -a } if b < 0 { b = -b } q := 0 for shift := 31; shift >= 0; shift-- { // 从大到小试：能减去 b·2^shift 就减 if (a >> shift) >= b { a -= b << shift q += 1 << shift } } if neg { return -q } return q }
$ go build -o bin . && ./bin < cases.jsonl [10,3] → 3 [7,-3] → -2 [-7,3] → -2 [-7,-3] → 2 [0,5] → 0 [1,1] → 1
JavaScript · 解法代码function divide(dividend, divisor) { if (dividend === -(2 ** 31) && divisor === -1) return 2 ** 31 - 1; // 唯一会溢出的情形 const neg = (dividend < 0) !== (divisor < 0); let a = Math.abs(dividend); const b = Math.abs(divisor); let q = 0; for (let shift = 31; shift >= 0; shift--) { // 从大到小试：能减去 b·2^shift 就减 const t = b * 2 ** shift; // 乘 2 的幂在双精度里是精确的；不用 <<，它只有 32 位 if (t <= a) { a -= t; q += 2 ** shift; } } return neg ? -q : q; }
$ node run.js < cases.jsonl [10,3] → 3 [7,-3] → -2 [-7,3] → -2 [-7,-3] → 2 [0,5] → 0 [1,1] → 1
C++ · 解法代码#include <climits> #include <cstdlib> using namespace std; class Solution { public: int divide(int dividend, int divisor) { if (dividend == INT_MIN && divisor == -1) return INT_MAX; // 唯一会溢出的情形 bool neg = (dividend < 0) != (divisor < 0); long long a = llabs((long long)dividend), b = llabs((long long)divisor); // 先转 long long，再取绝对值 long long q = 0; for (int shift = 31; shift >= 0; shift--) { // 从大到小试：能减去 b·2^shift 就减 if ((a >> shift) >= b) { a -= b << shift; q += 1LL << shift; } } return (int)(neg ? -q : q); } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [10,3] → 3 [7,-3] → -2 [-7,3] → -2 [-7,-3] → 2 [0,5] → 0 [1,1] → 1
共 20 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 20/20 Java 通过 20/20 Go 通过 20/20 JavaScript 通过 20/20 C++ 通过 20/20
除数取 1（这样商等于被除数，逐次相减要循环最多的次数），被除数分别取 10 万、100 万、1000 万，每个取三次中最快的一次：
除数为 1、被除数不同时，逐次相减 vs 移位相减（每个取三次中最快） 被除数 100000: 逐次相减 2.138 ms（循环 100000 次） 移位相减 0.0014 ms（循环 32 次） 结果一致=True 被除数 1000000: 逐次相减 21.437 ms（循环 1000000 次） 移位相减 0.0014 ms（循环 32 次） 结果一致=True 被除数 10000000: 逐次相减 218.104 ms（循环 10000000 次） 移位相减 0.0015 ms（循环 32 次） 结果一致=True
逐次相减的耗时与商成正比：被除数每增加 10 倍，耗时也增加约 10 倍（2.1ms、21.4ms、218.1ms）。移位相减永远只循环 32 次，耗时约 0.0014ms，与被除数的大小无关。被除数取到最大的 21 亿时，逐次相减要循环 21 亿次，这里没有运行，按上面的线性关系估算，在 Python 里要几十秒，这只是估算，不是实测。
Python 版本另外和大整数整除做了随机对拍，被除数和除数各自随机取 1 位到 31 位宽的正负整数，并有 5% 的概率取到 32 位整数的端点：
随机对拍 20000 组（被除数、除数各自随机取 1 位到 31 位宽的正负整数（含 -2^31 和 2^31-1 两个端点），除数不为 0），solve 与 brute 的结果全部一致。
另外四种语言只在上面 20 组固定用例上验证过，其中包含所有边界情形，没有做大规模随机对拍。
下面的演示用 43 ÷ 5。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示的最终结果与 solve 的返回值一致。从 shift = 31 到 4，5 · 2^shift 都比 43 大，全部跳过；shift = 3 时 5 · 8 = 40 ≤ 43，减去它，商加上 8，剩下的 3 小于 5，结束，43 ÷ 5 = 8。