What is the core pattern in Divide Two Integers?

The core pattern is math plus bit manipulation. You simulate division by repeatedly subtracting the largest power-of-two multiple of the divisor that still fits inside the remaining dividend.

Why is repeated subtraction alone a bad solution for Divide Two Integers?

Plain repeated subtraction can take one step per unit of the quotient, which is far too slow when the divisor is 1 or -1. Bit shifts let you remove large multiples at once, which is the whole optimization.

Why is INT_MIN such a problem in this question?

In 32-bit signed integers, INT_MIN has no positive counterpart, so negating it overflows. That is why many correct solutions keep values negative during processing or use a wider type.

How do you handle negative results correctly?

Track whether dividend and divisor have opposite signs, compute the quotient magnitude with shifted subtraction, then apply the sign once at the end. This preserves truncation toward zero instead of accidentally flooring negative answers.

What time complexity should I state for the bit manipulation solution?

For the common shifting-and-subtracting implementation, O((log n)^2) is a safe answer because you may scan shifts for each large subtraction round. If you precompute shifted candidates once, you can describe it closer to O(log n) with O(1) extra space.

#29

Medium

auto_awesome数学·位运算

LeetCode 题解工作台

两数相除

给你两个整数，被除数 dividend 和除数 divisor 。将两数相除，要求不使用乘法、除法和取余运算。整数除法应该向零截断，也就是截去（ truncate ）其小数部分。例如， 8.345 将被截断为 8 ， -2.7335 将被截断至 -2 。返回被除数 dividend 除以除数…

数学位运算

题目描述

给你两个整数，被除数 dividend 和除数 divisor。将两数相除，要求 不使用 乘法、除法和取余运算。

整数除法应该向零截断，也就是截去（truncate）其小数部分。例如，8.345 将被截断为 8 ，-2.7335 将被截断至 -2 。

返回被除数 dividend 除以除数 divisor 得到的商。

注意：假设我们的环境只能存储 32 位 有符号整数，其数值范围是 [−2³¹, 2³¹− 1] 。本题中，如果商 严格大于 2³¹− 1 ，则返回 2³¹− 1 ；如果商 严格小于 -2³¹ ，则返回 -2³¹。

示例 1:

输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = 3.33333.. ，向零截断后得到 3 。

示例 2:

输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = -2.33333.. ，向零截断后得到 -2 。

提示：

-2³¹ <= dividend, divisor <= 2³¹ - 1
divisor != 0

lightbulb

解题思路

方法一：模拟 + 快速幂

除法本质上就是减法，题目要求我们计算出两个数相除之后的取整结果，其实就是计算被除数是多少个除数加上一个小于除数的数构成的。但是一次循环只能做一次减法，效率太低会导致超时，可借助快速幂的思想进行优化。

需要注意的是，由于题目明确要求最大只能使用 32 位有符号整数，所以需要将除数和被除数同时转换为负数进行计算。因为转换正数可能会导致溢出，如当被除数为 INT32_MIN 时，转换为正数时会大于 INT32_MAX。

假设被除数为 $a$ ，除数为 $b$ ，则时间复杂度为 $O(\log a \times \log b)$ ，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
They expect you to replace repeated subtraction with doubling or left shifts, not brute force loops.
question_mark
They are checking whether you know why INT_MIN cannot be safely negated in 32-bit signed arithmetic.
question_mark
They want truncation toward zero exactly, especially for mixed-sign inputs like 7 and -3.

warning

常见陷阱

外企场景

error
Taking abs(INT_MIN) in a 32-bit type and silently overflowing before the real logic even starts.
error
Using floor-style behavior for negatives and returning -3 for 7 divided by -3 instead of the required -2.
error
Shifting the divisor too far without checking bounds, which can break comparisons or create incorrect subtraction steps.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return both quotient and remainder while still avoiding multiplication, division, and mod.
arrow_right_alt
Implement the same Divide Two Integers logic recursively by subtracting the largest doubled divisor each call.
arrow_right_alt
Generalize the bit-doubling idea to other repeated subtraction problems where powers of two compress the search.

help

常见问题

外企场景

继续练习

#67 二进制求和 #89 格雷编码 #231 2 的幂