0029. Divide Two Integers ========================= 题目信息 -------- :题号: 0029. 两数相除 :难度: Medium :主题: 整数、倍增、二进制、贪心、溢出 :原题: `LeetCode 0029 `_ :重点: 从逐次减法推导到按二进制位试商,并安全处理向零截断、符号和 32 位边界 题目重述 -------- 给定两个 32 位有符号整数 ``dividend`` 和 ``divisor``,计算整数商并返回。不得使用乘法、除法和取模运算符。 结果的小数部分必须向零截断。例如 ``7 / -3`` 返回 ``-2``,而不是向下取整得到 ``-3``。题目保证 ``divisor != 0``。 输入范围为 ``[-2^31, 2^31 - 1]``。若数学结果超过 32 位有符号整数范围,只会发生在 ``INT_MIN / -1``,此时必须返回 ``INT_MAX``。 自建示例 -------- * 正数且有余数:``dividend = 58``、``divisor = 7``,返回 ``8``,因为 ``58 = 7 * 8 + 2``; * 异号并向零截断:``dividend = -58``、``divisor = 7``,返回 ``-8``; * 被除数绝对值较小:``dividend = 3``、``divisor = 5``,返回 ``0``; * 最小负数:``dividend = INT_MIN``、``divisor = 1``,返回 ``INT_MIN``; * 唯一溢出:``dividend = INT_MIN``、``divisor = -1``,返回 ``INT_MAX``。 C++ 实现 -------- .. code-block:: cpp #include class Solution { private: long long magnitude(int value) { return value < 0 ? -static_cast(value) : static_cast(value); } int applySignAndClamp(long long quotient, bool negative) { if (!negative && quotient > INT_MAX) { return INT_MAX; } const long long signedQuotient = negative ? -quotient : quotient; return static_cast(signedQuotient); } int repeatedSubtraction(int dividend, int divisor) { long long remaining = magnitude(dividend); const long long base = magnitude(divisor); long long quotient = 0; while (remaining >= base) { remaining -= base; ++quotient; } const bool negative = (dividend < 0) != (divisor < 0); return applySignAndClamp(quotient, negative); } int repeatedDoubling(int dividend, int divisor) { long long remaining = magnitude(dividend); const long long base = magnitude(divisor); long long quotient = 0; while (remaining >= base) { long long chunk = base; long long contribution = 1; while ((chunk << 1) <= remaining) { chunk <<= 1; contribution <<= 1; } remaining -= chunk; quotient += contribution; } const bool negative = (dividend < 0) != (divisor < 0); return applySignAndClamp(quotient, negative); } int binaryLongDivision(int dividend, int divisor) { long long remaining = magnitude(dividend); const long long base = magnitude(divisor); long long quotient = 0; for (int bit = 31; bit >= 0; --bit) { const long long chunk = base << bit; if (chunk <= remaining) { remaining -= chunk; quotient += 1LL << bit; } } const bool negative = (dividend < 0) != (divisor < 0); return applySignAndClamp(quotient, negative); } public: int divide(int dividend, int divisor) { return binaryLongDivision(dividend, divisor); } }; 题解 ---- 除法的直接含义 ~~~~~~~~~~~~~~ 先忽略符号。若不断从 ``|dividend|`` 中减去 ``|divisor|``,能够成功减去的次数就是商的绝对值;当剩余量小于 除数绝对值时停止,未被消去的部分就是余数。 ``repeatedSubtraction`` 直接实现这一含义。每次循环保持: .. code-block:: text |dividend| = |divisor| * quotient + remaining 循环结束时 ``0 <= remaining < |divisor|``,因此 ``quotient`` 正是绝对值除法向下取整后的结果。最后再恢复符号, 就得到题目要求的向零截断商。 这个方法的问题不在正确性,而在每轮只增加 ``1``。例如 ``INT_MAX / 1`` 需要超过二十亿轮,时间与商的数值 大小成正比。 倍增删除重复减法 ~~~~~~~~~~~~~~~~ 一次减去一个除数过慢,可以通过加法倍增构造: .. code-block:: text divisor, 2 * divisor, 4 * divisor, 8 * divisor, ... 代码不使用乘法,而是让 ``chunk`` 和对应的 ``contribution`` 同时左移一位。若当前剩余量至少容纳两倍 ``chunk``,就继续倍增;否则当前 ``chunk`` 是本轮能够减去的最大二次幂倍数。 以 ``58 / 7`` 为例,第一轮依次得到 ``7、14、28、56``,一次减去 ``56``,商增加 ``8``,剩余 ``2``。 这相当于把八次重复减法压缩为一次减法和若干次倍增。 ``repeatedDoubling`` 每轮都从 ``base`` 重新构造最大倍数。外层最多执行 ``O(log |quotient|)`` 轮,每轮又可能 倍增 ``O(log |quotient|)`` 次,因此最坏时间为 ``O(log² |quotient|)``。 商的二进制分解 ~~~~~~~~~~~~~~ 逐轮倍增仍在重复构造同一组二次幂倍数。商本身可以写成若干二次幂之和,例如: .. code-block:: text 13 = 8 + 4 + 1 = 1101₂ 因此可以从最高位到最低位直接判断商的每一位是否为 ``1``。对于位 ``bit``,候选除数倍数为 ``base << bit``: * 候选不大于当前剩余量时,该位可以取 ``1``,减去候选并把 ``1 << bit`` 加入商; * 候选大于当前剩余量时,该位只能取 ``0``,继续检查更低位。 处理完某一位后,更高位已经固定,剩余量只需要由更低位对应的倍数继续表示。这就是整数长除法在二进制中的形式。 降序试商 ~~~~~~~~ 必须从高位向低位判断。若最高可行位没有选入,只靠所有更低位之和也无法得到更大的合法商;选入后,算法再用 低位填充剩余量,最终得到不超过被除数绝对值的最大除数倍数。 以 ``58 / 7`` 为例: .. list-table:: :header-rows: 1 * - 商位 - 候选倍数 - 剩余量 - 动作 * - ``2^3`` - ``7 << 3 = 56`` - 58 - 选入,商变为 8,剩余 2 * - ``2^2`` - 28 - 2 - 跳过 * - ``2^1`` - 14 - 2 - 跳过 * - ``2^0`` - 7 - 2 - 跳过 最终商为 ``8``。剩余量 ``2`` 小于除数 ``7``,不能再增加任何商位。 固定扫描范围 ~~~~~~~~~~~~ 两个输入都是 32 位整数,商的绝对值最大为 ``2^31``,所以只需要检查 ``bit = 31`` 到 ``0`` 共 32 个位置。 ``base`` 最大为 ``2^31``。计算 ``base << 31`` 时最大得到 ``2^62``,仍在 64 位有符号整数范围内。使用 ``long long`` 保存绝对值、候选倍数和商,可以安全表示 ``|INT_MIN| = 2^31``,也避免对 ``INT_MIN`` 直接取 32 位绝对值产生溢出。 符号与截断方向 ~~~~~~~~~~~~~~ 主体算法只计算: .. code-block:: text floor(|dividend| / |divisor|) 若两个输入符号不同,就对这个非负商取负。余数始终被直接舍弃,没有在负数结果上再减一,因此结果向零截断。 例如 ``-58 / 7`` 的绝对值商为 ``8``,恢复符号后得到 ``-8``。 两个输入是否异号可由 ``(dividend < 0) != (divisor < 0)`` 判断。零既不小于零,也不会造成符号歧义。 唯一溢出 ~~~~~~~~ 32 位正数最大值为 ``2^31 - 1``,负数最小值为 ``-2^31``。只有 ``INT_MIN / -1`` 会产生正数 ``2^31``, 超过 ``INT_MAX``;其他商都能放入 32 位有符号整数。 ``applySignAndClamp`` 在恢复正号前检查这一情况并返回 ``INT_MAX``。当结果为负数 ``-2^31`` 时,它仍是合法的 ``INT_MIN``,可以安全转换回 ``int``。 代码演进 ~~~~~~~~ ``repeatedSubtraction`` 每轮只删除一个除数,代码直接对应除法定义,但运行次数等于商的绝对值。 ``repeatedDoubling`` 用左移构造二次幂倍数,一轮可以替代大量重复减法;它删除了线性于商的循环,却会在每个外层 阶段重新从 ``base`` 开始倍增。 ``binaryLongDivision`` 直接枚举商的 32 个二进制位。逐轮重新构造倍数的内层循环消失,每个候选位只计算一次, 同时不再需要保存倍增表。公开入口采用这一方法。 复杂度分析 ~~~~~~~~~~ .. list-table:: :header-rows: 1 * - 方法 - 时间复杂度 - 工作空间 - 主要代价 * - 重复减法 - ``O(|quotient|)`` - ``O(1)`` - 每次只消去一个除数 * - 逐轮倍增 - ``O(log² |quotient|)`` - ``O(1)`` - 每轮重新寻找最大二次幂倍数 * - 二进制长除法 - ``O(log C)`` - ``O(1)`` - 从高到低检查固定整数范围内的商位 ``C`` 表示整数取值范围;对固定 32 位输入,主解法始终检查 32 个商位,因此运行次数具有常数上界。