Chapter 3
Optional read: How does division work?

Chapter 3 built the machine’s first arithmetic operation: addition. This optional read asks how the same ingredients stretch to division. You can skip it and continue to memory; nothing later depends on the details. But it is a useful test of the idea that complicated arithmetic is not magic, only a small operation repeated carefully.

Division looks unlike addition in decimal because schoolbook long division has more ceremony: try a digit, multiply back, subtract, bring the next digit down. In binary the ceremony collapses. Each quotient digit can only be 0 or 1. At each step the divider asks one question: is the running remainder at least as large as the divisor? If yes, subtract the divisor and write a 1 in the quotient. If no, write a 0 and move on.

3.1 Subtraction from addition

The divider needs subtraction, but the hardware already has an adder. Fixed-width binary numbers make this cheap. To compute a-b, invert every bit of b, add one, and add that to a. This is two’s complement subtraction. The final carry out is discarded; the remaining fixed-width bits are the answer. The only catch is that this chapter stays unsigned, so it refuses a subtraction that would go below zero.

Example 3-1. Unsigned subtraction by adding two’s complement

def subtract_unsigned(a_bits: list[int], b_bits: list[int]) -> list[int]:
    """Subtract b from a as an unsigned fixed-width value.

    Raise if the result would be negative. Otherwise return a result with the
    same width as the wider input.
    """
    width = max(len(a_bits), len(b_bits))
    a = _pad(a_bits, width)
    b = _pad(b_bits, width)
    if compare_unsigned(a, b) < 0:
        raise ValueError("unsigned subtraction would be negative")
    inverted = [not_(bit) for bit in b]1
    one = [HIGH] + [LOW] * (width - 1)
    twos = ripple_add(inverted, one)[:width]2
    return ripple_add(a, twos)[:width]3

• invert every bit of the subtrahend
• add one with Chapter 3’s ripple adder to form the two’s-complement value
• add it to the minuend and keep the fixed-width low bits

3.2 Bring one bit down

Now long division becomes a loop over the dividend bits, from most significant to least significant. The remainder starts at zero. Each step shifts that remainder left by one place and drops the next dividend bit into the empty low bit. That is the binary version of bringing down the next digit.

If the new remainder is at least the divisor, the divider subtracts the divisor and writes a 1 into the quotient at that bit position. Otherwise it leaves the remainder alone and the quotient bit stays 0. Figure 3.2 shows the whole run for 13 / 3: the dividend is 1101, the divisor is 0011, and the result is quotient 0100 with remainder 1.

Example 3-2. Unsigned binary division

def divide_unsigned(dividend: int, divisor: int, width: int,
                    trace: list | None = None) -> tuple[int, int]:
    """Divide `dividend` by `divisor`, returning (quotient, remainder).

    Both inputs are unsigned values that must fit in `width` bits. The algorithm
    scans the dividend from most significant bit to least significant bit, just
    like long division reads digits left to right.
    """
    _check_inputs(dividend, divisor, width)
    dividend_bits = to_bits(dividend, width)
    divisor_bits = to_bits(divisor, width)
    remainder = [LOW] * width
    quotient = [LOW] * width

    for bit in range(width - 1, -1, -1):
        remainder = [dividend_bits[bit]] + remainder[:-1]1
        if compare_unsigned(remainder, divisor_bits) >= 0:2
            remainder = subtract_unsigned(remainder, divisor_bits)
            quotient[bit] = HIGH3
        if trace is not None:
            trace.append({
                "bit": bit,
                "remainder": from_bits(remainder),
                "quotient": from_bits(quotient),
            })

    return from_bits(quotient), from_bits(remainder)

• shift the running remainder left and bring down the next dividend bit
• the only decision: is the remainder large enough to subtract the divisor?
• after a successful subtraction, mark that quotient bit as 1

3.3 Division, run

Running ftb.division divides 13 by 3 and prints the state after each bit.

BINARY DIVIDE: 13 / 3
bit brought down | quotient so far | remainder
-----------------+-----------------+----------
       3         |        0        |     1
       2         |        4        |     0
       1         |        4        |     0
       0         |        4        |     1

result: quotient 4, remainder 1
check: 3 * 4 + 1 = 13

The quotient stays zero until the running remainder has enough value to subtract 3. At bit 2 it can, so the divider subtracts and writes that quotient bit. The final line checks the result in the form every division must satisfy: \[ \text {divisor} \times \text {quotient} + \text {remainder} = \text {dividend}. \]

Real processors use faster divider circuits, handle signed numbers, and also divide fractions. This chapter leaves those out. The core integer idea is already here: division is repeated shift, compare, subtract, and record the bit.

Exercises

• Divide 15 by 5 by hand in binary. Which quotient bits become 1?
• What should the divider do if the divisor is zero?
• Change the example to divide 14 by 3, and predict the remainder before running it.