Binary division

Shift, subtract, and the quotient

11 min read

Binary division computes a quotient and a remainder by shift-and-subtract, the hardware form of long division: for each bit from the top, shift the running remainder, try to subtract the divisor, and if it fits set that quotient bit to 1 and keep the subtraction, otherwise set it to 0 and restore.

Builds onNegative numbers and subtraction The barrel shifter Binary multiplication

You have three of the four arithmetic operations in hardware: an adder adds, the two's-complement trick subtracts, and shift-and-add multiplies. Division is the fourth, and it is the trickiest. Where multiplication is shift-and-add, division runs the same idea backwards as shift-and-subtract, and instead of one clean pass it needs a decision at every step.

It is exactly the long division you did on paper, only easier per step. In decimal long division you eyeball "how many times does 7 go into 34?" and it could be anything from 0 to 9. In binary the divisor either fits once or not at all, so every step is a single yes/no question: does the divisor fit? That yes/no answer *is* the next quotient bit.

The easy case: dividing by a power of two is a shift

One special case is almost free. Just as multiplying by 2^k is a left shift, **dividing by 2^k is a right shift by k**: the bits you shift off the bottom are the remainder, and what stays is the quotient. For example 13 (1101) divided by 4 (2^2) is a right shift by 2: the top bits 0011 (3) are the quotient and the two bits shifted off, 01, are the remainder 1. Check: 3 * 4 + 1 = 13.

That shortcut only works when the divisor is a power of two. Divide by 3, 5, 10, or any non-power-of-two and there is no single shift that does it; you need the real algorithm below. This is the mirror of the multiplier lesson, where x * 8 was a free shift but x * 3 needed the full shift-and-add.

Restoring long division in binary

For a general divisor, hardware walks the dividend from its most-significant bit down, keeping a running remainder. At each step it brings the next dividend bit into the remainder, tries subtracting the divisor, and uses the sign of the result to decide the quotient bit. The most straightforward version is restoring division: if the trial subtraction goes negative, you undo it (restore the old remainder) before moving on.

Start with the remainder at 0 and take the dividend's bits from the most-significant end.
Shift the remainder left by one and bring in the next dividend bit at the bottom.
Try to subtract the divisor from the remainder.
If the result is not negative, the divisor fit: set this quotient bit to 1 and keep the subtracted result.
If the result went negative, it did not fit: set this quotient bit to 0 and restore the remainder (add the divisor back).
Repeat for every dividend bit. The quotient bits (first one is most-significant) are the quotient; whatever is left in the remainder is the remainder.

Worked example: 13 / 3

Divide 13 by 3: in binary that is 1101 / 11. The divisor is 3 (0011). Take the dividend's bits from the top, 1, 1, 0, 1, and run the four steps. "R" is the running remainder; each trial subtracts 3:

dividend bit in	R (after shift-in)	trial R - 3	fits (>= 0)?	quotient bit	R kept
1	0001 (1)	1 - 3 = -2	no	0	0001 (1)
1	0011 (3)	3 - 3 = 0	yes	1	0000 (0)
0	0000 (0)	0 - 3 = -3	no	0	0000 (0)
1	0001 (1)	1 - 3 = -2	no	0	0001 (1)

Restoring division of 13 / 3. Read the quotient bits top to bottom (most-significant first): 0, 1, 0, 0, which is 0100 = 4. The remainder left at the end is 1. Each 'no' row restores R (the trial is thrown away); each 'yes' row keeps the subtracted value.

1101 / 11 = 100 remainder 1 (13 / 3 = 4 r 1; check: 4 * 3 + 1 = 13)

So 13 / 3 gives quotient 4 (100) and remainder 1, and the check 4 * 3 + 1 = 13 confirms it. Notice the shape of the answer: every step emitted exactly one quotient bit, and the leftover that could not be divided further is the remainder. That quotient * divisor + remainder = dividend identity is the definition division must always satisfy.

The engine doing the real work each step is a subtractor, the very adder/subtractor you already built. Division just drives it in a loop: subtract the divisor from the remainder, look at whether the result went negative, and decide the quotient bit from that sign.

The core of a divider is a subtractor. This is the 8-bit adder/subtractor (ADDSUB8) from the subtraction lesson with SUB = 1, computing A - B. In a divider, A is the running remainder and B is the divisor: each step subtracts, and the sign of the result decides the quotient bit (fit or not). Open it in the lab and subtract a divisor from a remainder to see when it 'fits'.

Restoring in hardware: undo the trial when it overshoots

On paper you can glance at the remainder and decide whether the divisor fits before you commit. Hardware cannot glance: it subtracts first and looks afterward. Each step the subtractor computes remainder - divisor and writes that result straight back into the remainder register, and then a single sign test asks whether it went negative. If it did not, the divisor fit: the machine keeps the difference and records a 1 quotient bit. If it did go negative, the divisor did not fit, and the remainder register is now holding the wrong (over-subtracted) value, so the machine adds the divisor straight back to recover exactly what was there before the trial, and records a 0 quotient bit. That add-back is the restore, and it is the step the method is named for.

Every step that does not fit costs one extra addition just to undo the trial subtraction. That wasted work is exactly what non-restoring division (described below) removes: instead of adding the divisor back, it lets the remainder stay negative and corrects on the following step.

Shift the remainder, not the divisor

There are two ways to keep the divisor lined up with the right slice of the dividend as you march down the bits. The obvious one holds the divisor in the top of a double-width register and shifts the divisor one place right every step; but that needs a 2n-bit divisor register and a full 2n-bit subtractor, most of whose bits sit idle. The better datapath does the opposite: it shifts the remainder one place left each step and subtracts the n-bit divisor from just the top half of the remainder register. Now the divisor register and the subtractor are only n bits wide (half the hardware) and nothing is wasted. This is the same width trick the multiplier used when it shifted the running product instead of widening the multiplicand.

Shifting the remainder left instead of the divisor right cuts the divisor register and the subtractor from 2n bits down to n. And just as the multiplier merged its product and multiplier into one shifting register, a divider can let quotient bits fill the low bits of the remainder register as they empty out, so no separate quotient register is needed: when the loop ends, the top half holds the remainder and the bottom half holds the quotient.

Worked trace: 5 / 2 in the registers

Watch that optimized datapath divide 5 by 2 (101 / 10). The remainder register R is 6 bits, shown as a top half RU and a bottom half RL; it starts with the dividend in the bottom, R = 000 101, and the divisor is D = 010 (2). Each of the three steps shifts R left by one, subtracts D from the top half RU, then keeps or restores based on the sign, writing the quotient bit into the bottom bit as it opens up:

step	R after shift left (RU \| RL)	trial RU - D	sign	quotient bit	R after step (RU \| RL)
1	001 \| 010	1 - 2 = -1	neg	0 (restore)	001 \| 010
2	010 \| 100	2 - 2 = 0	>= 0	1 (keep)	000 \| 101
3	001 \| 010	1 - 2 = -1	neg	0 (restore)	001 \| 010

Optimized restoring division of 5 / 2. R starts at 000 101. Each step shifts R left, subtracts D = 2 from the top half RU, and on a negative result adds D back (restore) and writes a 0, otherwise keeps the difference and writes a 1 into the freed bottom bit. After three steps the top half RU = 001 is the remainder 1 and the bottom half RL = 010 is the quotient 2. Check: 2 * 2 + 1 = 5.

So 5 / 2 = 2 remainder 1. Steps 1 and 3 each went negative and paid for a restore (add 2 back), while step 2 kept its subtraction and set a 1. Notice there is no separate quotient register in the trace at all: the quotient assembled itself in the bottom half RL as the dividend bits shifted up and out, exactly the register-merging trick the multiplier used.

Division is the slowest of the four operations, and the reason is structural: an adder or multiplier array can produce its result in one combinational pass, but division is inherently iterative, one quotient bit per step, so an n-bit divide takes about n steps and is usually multi-cycle in a real CPU (it ties up the datapath for several clocks). It is also the operation with a special failure: dividing by 0 has no answer, so hardware raises a divide-by-zero exception rather than returning a number.

Two refinements are worth naming. Non-restoring division avoids the restore step: instead of adding the divisor back after a negative result, it leaves the remainder negative and *adds* the divisor on the next step, which trades the restore for slightly trickier bookkeeping and is what many real dividers use. And signed division is handled by dividing the magnitudes and then fixing the signs of the quotient and remainder afterward, the same divide-magnitudes-then-correct idea Booth's method uses for signed multiplication.

Common mistakes. Never divide by 0: it is undefined and must be caught, not computed. Do signed division on the magnitudes and fix the signs at the end, rather than feeding negatives straight into the subtract loop. Watch the iteration count: an n-bit dividend needs n steps, and stopping one short drops the last quotient bit. Do not confuse the two outputs, either: division produces both a quotient and a remainder, and the identity quotient * divisor + remainder = dividend is what checks your work. Finally, the right-shift shortcut only divides by a power of two; reaching for it with any other divisor gives the wrong answer.

Try it

Divide 11 by 3 using restoring binary division (1011 / 11). Walk the four steps, tracking the remainder, and give the quotient and remainder. Then check your answer.

With division you have the full set of arithmetic operations, add, subtract, multiply, and divide, built from the same handful of primitives (adders, subtractors, and shifts). The ALU gathers the fast single-pass operations into one block, while multiply and divide, being iterative, are often separate multi-cycle units the CPU steps through under control.

Frequently asked

How does a computer divide binary numbers?

By shift-and-subtract, the hardware form of long division. It walks the dividend from the most-significant bit, keeping a running remainder: each step shifts the remainder and brings in the next dividend bit, tries to subtract the divisor, and sets the quotient bit to 1 (keeping the subtraction) if the divisor fit or 0 (restoring the remainder) if it did not. After all bits, the collected quotient bits are the quotient and what is left is the remainder.

What is restoring division?

Restoring division is the simplest shift-subtract division method. At each step it subtracts the divisor from the remainder; if the result is negative the divisor did not fit, so it sets that quotient bit to 0 and restores the old remainder by adding the divisor back. Non-restoring division skips that add-back by leaving the remainder negative and compensating on the next step, which is a bit faster.

Why is division slower than multiplication?

Because it is inherently iterative. A multiplier can form all its partial products at once and sum them in a single combinational pass, but division must discover one quotient bit at a time, since each bit depends on whether the previous subtraction fit. An n-bit divide takes about n sequential steps, so real CPUs implement it as a multi-cycle operation.

What happens when you divide by zero?

Dividing by zero has no meaningful result, so hardware does not return a number: it raises a divide-by-zero exception (a fault the CPU signals). Division circuits detect a zero divisor before or during the operation and flag it rather than producing garbage.

Every lesson here builds toward one thing: a working CPU, from the transistor up.

Open the free lab →