# Binary division

*Shift, subtract, and the quotient*

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.

Group: Arithmetic
URL: https://digiwleea.wleeaf.dev/learn/divider/

You have three of the four arithmetic operations in hardware: an [adder](https://digiwleea.wleeaf.dev/learn/adder8/) adds, the [two's-complement](https://digiwleea.wleeaf.dev/learn/subtract/) trick subtracts, and shift-and-add [multiplies](https://digiwleea.wleeaf.dev/learn/multiplier/). **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.

> **TIP:** 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](https://digiwleea.wleeaf.dev/learn/shifter/), **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`.

> **KEY:** 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](https://digiwleea.wleeaf.dev/learn/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.

1. Start with the remainder at `0` and take the dividend's bits from the most-significant end.
2. Shift the remainder left by one and bring in the next dividend bit at the bottom.
3. Try to subtract the divisor from the remainder.
4. If the result is **not negative**, the divisor fit: set this quotient bit to `1` and keep the subtracted result.
5. If the result **went negative**, it did not fit: set this quotient bit to `0` and restore the remainder (add the divisor back).
6. 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](https://digiwleea.wleeaf.dev/learn/subtract/) 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.

_Circuit diagram: 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.

> **TIP:** 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](https://digiwleea.wleeaf.dev/learn/multiplier/) used when it shifted the running product instead of widening the multiplicand.

> **KEY:** 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.

> **KEY:** Division is the slowest of the four operations, and the reason is structural: an [adder](https://digiwleea.wleeaf.dev/learn/adder8/) or [multiplier](https://digiwleea.wleeaf.dev/learn/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.

> **WARN:** **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.

**Q (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.

**A:** Dividend bits from the top are `1, 0, 1, 1`; the divisor is `3`. Step 1 (bring in `1`): `R = 1`, and `1 - 3 = -2` is negative, so quotient bit `0`, restore `R = 1`. Step 2 (bring in `0`): `R = 10` (`2`), and `2 - 3 = -1` is negative, so quotient bit `0`, restore `R = 2`. Step 3 (bring in `1`): `R = 101` (`5`), and `5 - 3 = 2` is not negative, so quotient bit `1`, keep `R = 2`. Step 4 (bring in `1`): `R = 101` (`5`), and `5 - 3 = 2` is not negative, so quotient bit `1`, keep `R = 2`. The quotient bits top to bottom are `0011` = `3`, and the remainder is `2`. Check: `3 * 3 + 2 = 11`.

> **KEY:** With division you have the full set of arithmetic operations, add, subtract, [multiply](https://digiwleea.wleeaf.dev/learn/multiplier/), and divide, built from the same handful of primitives (adders, subtractors, and shifts). The [ALU](https://digiwleea.wleeaf.dev/learn/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](https://digiwleea.wleeaf.dev/learn/control/).

### FAQ

**Q:** How does a computer divide binary numbers?

**A:** 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.

**Q:** What is restoring division?

**A:** 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.

**Q:** Why is division slower than multiplication?

**A:** 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.

**Q:** What happens when you divide by zero?

**A:** 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.