Divide two integers: shifts, carries and 32 bits

Dividing two integers without the division operator means building the quotient from shifts, subtraction and comparisons, the way long division works on paper, but in base 2: the quotient is a sum of powers of two, so the divisor shifted left by k is subtracted whenever it still fits, for k from 31 down to 0. Adding without + works one level lower: XOR adds bits without carrying, and AND shows where the carries are. Interviews ask both because the ideas are short and the 32-bit edges are not: the one quotient that overflows, Python’s integers that never do, and JavaScript’s doubles. Here are both problems, their brute force with its cost, and what to notice.

Two problems for a chip without a divider

A metering chip has no divide or multiply instruction, and its firmware must do the arithmetic by hand.

Problem A: divide two integers. Given 32-bit signed integers a and b, with b ≠ 0, return a / b rounded toward zero, as C, Java and Go round an integer quotient, using only addition, subtraction, comparisons and bit operations. The quotient −2³¹ / −1 does not fit in 32 bits; return 2³¹ − 1 for it.

• 100 / 7 gives 14, and 7 / −2 gives −3.
• −2147483648 / −1 gives 2147483647, and 0 / 5 gives 0.

Problem B: add two integers. Given 32-bit signed a and b, return their sum with 32-bit wraparound, as a Java int would hold it, using only bit operations.

• 5 + 9 gives 14, and −3 + 1 gives −2.
• 2147483647 + 1 gives −2147483648.

The brute force, and why it fails at these sizes

Subtract the divisor until it no longer fits, and count the subtractions; add by incrementing one step at a time:

# Both problems by brute force. A: subtract the divisor until it no longer fits, counting the subtractions.
# B: add b to a one step at a time with a bitwise increment, which needs no + at all.

INT_MIN, INT_MAX = -(2**31), 2**31 - 1


def divide_by_subtracting(a, b):
    """Problem A: a / b rounded toward zero, by repeated subtraction, and the subtractions it took."""
    if a == INT_MIN and b == -1:
        return INT_MAX, 0
    negative = (a < 0) != (b < 0)
    a, b = abs(a), abs(b)
    q = 0
    while a >= b:
        a -= b
        q += 1
    return (-q if negative else q), q


def increment(x):
    """x + 1 with bit operations: flip the trailing 1s to 0 and the lowest 0 to 1."""
    bit = 1
    while x & bit:
        x ^= bit
        bit <<= 1
    return x | bit


def add_by_counting(a, b):
    """Problem B for b >= 0: increment a, b times."""
    for _ in range(b):
        a = increment(a)
    return a


for a, b in ((100, 7), (7, -2), (0, 5), (-2147483648, -1)):
    q, steps = divide_by_subtracting(a, b)
    print(f"A: {a} / {b} -> {q}  ({steps:,} subtractions)")
print(f"A: -2147483648 / 1 would take {2**31:,} subtractions")
print("B: 5 + 9 ->", add_by_counting(5, 9), "  (9 increments)")
print(f"B: 1 + 2147483646 would take {2147483646:,} increments")

A: 100 / 7 -> 14  (14 subtractions)
A: 7 / -2 -> -3  (3 subtractions)
A: 0 / 5 -> 0  (0 subtractions)
A: -2147483648 / -1 -> 2147483647  (0 subtractions)
A: -2147483648 / 1 would take 2,147,483,648 subtractions
B: 5 + 9 -> 14   (9 increments)
B: 1 + 2147483646 would take 2,147,483,646 increments

The quotient of −2³¹ / 1 takes 2,147,483,648 subtractions, about 21 seconds of C++ for a single call if a simple step costs 10 nanoseconds, the rough figure of the constraints lesson, and minutes of Python. Adding 2,147,483,646 by increments is just as slow. Both need a number of steps that grows with the size of the operands, where the target is a fixed 32 or so.

What to notice

• In A, each bit of the quotient is one yes-or-no question: does b · 2ᵏ still fit into what is left of a? Asked from k = 31 down, that is 32 questions.
• In B, a + b equals (a ^ b) + ((a & b) << 1): the sum without carries plus the carries, which is another addition, with fewer carries each time.
• Python’s integers have no width, so neither 32-bit overflow nor the end of the carries happens by itself: the code must keep 32 bits explicitly.

Long division in binary, proved with an invariant Pro: opens with a Pro, Premium or Ultimate pass