1. Thinking Process

1.1. ⚙️ Step-by-step logic

• Handle signs

• The result is negative if exactly one of (dividend, divisor) is negative.

• You can check that with:

negative = (dividend < 0) ^ (divisor < 0)

• (xor between their signs)

Then take absolute values for simplicity:

• dividend = abs(dividend)

• divisor = abs(divisor)

• Example:

dividend = 43, divisor = 3

Double divisor until it almost exceeds 43:

3 << 0 = 3
3 << 1 = 6
3 << 2 = 12
3 << 3 = 24
3 << 4 = 48 (too big)

The largest valid shift is 3 (24 ≤ 43).

→ Subtract 24 and add 1 « 3 = 8 to quotient.

• Now dividend = 19, repeat the process.

• Continue until dividend < divisor

• Each iteration removes a large chunk of the dividend, so it’s efficient (O(log N)).

1.2. ⚠️ Edge Cases

1.2.1. Overflow

In 32-bit signed integer, max = 2^31−1, min = −2^31.

-2^31 ÷ -1 = 2^31 → overflow → clamp to 2^31−1.

1.2.2. Divisor = ±1

• Just return dividend or -dividend but handle overflow properly.

2. After-code walk-through

def divide(dividend: int, divisor: int) -> int:
    INT_MAX = 2**31 - 1
    INT_MIN = -2**31

    # Handle overflow
    if dividend == INT_MIN and divisor == -1:
        return INT_MAX

    # Sign of result
    negative = (dividend < 0) ^ (divisor < 0)
    dividend, divisor = abs(dividend), abs(divisor)

    quotient = 0

    while dividend >= divisor:
        shift = 0
        while dividend >= (divisor << (shift + 1)):
            shift += 1
        dividend -= divisor << shift
        quotient += 1 << shift

    return -quotient if negative else quotient

Walk-through:

• negative uses an XOR to decide the result’s sign. We then convert both operands to positive for simpler bit operations.

• The outer while a >= b maintains a as the remainder still to divide. The inner loop finds the largest 2^shift * b ≤ a by left-shifting («) until it would overshoot;

• Correctness: The algorithm subtracts non-overlapping, descending powers-of-two multiples of the divisor.

• Complexities: Each subtraction halves a, so at most O(log

  dividend

  ) iterations; constant extra space.