LeetCode 29. 两数相除:32 位整数下的位运算除法全解(doocs/leetcode 多语言实现)

原创2026-10-15 18:24:421,413 阅读
文章标签:示例工程

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 - 1
  • divisor != 0

思路分析:为什么朴素减法会超时

除法本质上就是减法。题目要求计算两数相除后的取整结果,本质上是计算:被除数由多少个除数、再加上一个小于除数的数构成。

最直观的做法是一次循环只做一次减法:只要被除数还能容纳一个除数,就从被除数中减去 1 × b,商加 1。但该做法的致命问题是:当 |a| 接近 2^31 时,需要循环约 2^31 次,必然超时,无法通过本题的时间限制。同时题目禁止使用乘法、除法与取余,因此必须另辟蹊径。

仓库题解给出的破局思路是快速幂(二进制倍增):

在剩余量仍够的前提下,将除数不断左移加倍,即可一次扣掉 2^k 倍,商按二进制累加。这与快速幂的思想一致。左移时还需防止溢出:若再翻倍会超出 32 位范围,则停止倍增。

换句话说,与其一次减去 1 × b,不如尝试一次减去 2^k × b 这种尽可能大的块:把除数 b 通过左移不断翻倍,找到「翻倍后仍不超过剩余被除数」的最大块,一次性扣除并累加对应的商,然后对剩余部分重复该过程。这样每次外循环都能扣掉一大块,循环次数被压缩到对数级别。

难点解析:32 位溢出与负数域运算

题目明确要求环境只能存储 32 位有符号整数,因此必须格外小心溢出:

  1. 不能把负数转成正数再运算。例如当被除数为 INT32_MIN(即 -2^31)时,转换为正数会得到 2^31,大于 INT32_MAX(2^31 - 1),直接溢出。
  2. 特判除数为 1:b == 1 时直接返回 a,无需进入循环。
  3. 特判唯一溢出场景:当 a == -2^31 且 b == -1 时,真实商为 2^31,超出 32 位有符号整数上界,必须按题目要求返回 2^31 - 1(即 INT_MAX)。
  4. 符号单独记录:先用 (a > 0 && b > 0) || (a < 0 && b < 0) 记录最终结果是否为正,然后把 a、b 统一转换为负数参与运算,全程在负数域上完成,从根源上规避取相反数导致的溢出。
  5. 左移防溢出:内层倍增循环中,必须确保 x 在左移后仍处于 32 位有符号范围内。各语言使用不同的防溢出写法(详见下文实现),例如 Python 判断 x >= -(2**30)、Java 判断 x >= (Integer.MIN_VALUE >> 1),其共同语义是「x 再翻倍不会越过 -2^31 下界」。

算法流程:二进制倍增逐块扣除

以负数域运算为例,核心流程如下:

  1. 特判 b == 1 返回 a;特判 a == -2^31 && b == -1 返回 2^31 - 1。
  2. 记录符号 sign,将 a、b 统一转为负数。
  3. 初始化商 ans = 0。
  4. 外层循环 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 倍)。
  5. 根据 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),仅使用常数个变量。
  • 正确性要点:
    1. 负数域运算保证了 a = -2^31 这类极端输入不会因取相反数而溢出;
    2. 特判 a == -2^31 && b == -1 保证商溢出时按题目要求钳制到 2^31 - 1;
    3. 内层倍增循环保证每次扣掉的 x 都是「不超过剩余被除数」的最大二进制块,商逐位按二进制累加,最终等价于向零截断的整数除法。

仓库文件导航

掌握「模拟 + 快速幂」的二进制倍增思想后,你还可以将其迁移到其他「禁止乘除 + 强溢出约束」的整数运算题目中;同类技巧在仓库的位运算与数学专题(可参考 solution/README.md 的题目索引)中反复出现,值得举一反三。

登录后查看全文
leetcode