Now we've seen how binary starts at registers flows through gates to, add, subtract, and multiply let's take a look at the last layer (for this series) division.
1st principles of binary division
CPUs don’t magically divide, they use the following logical operations.
- if...else: to check if the growing remainder >= divisor, to write down the quotient.
- subtract: to get the remainder.
- shift: to shift left by each index position moved down to write down the next LSB.
We always start at the MSB of the dividend and use if...else... to check if the growing remainder >= the divisor if that's true we write down 1 at the quotient else 0.
If and only if the growing remainder >= the divisor we subtract the divisor from the growing remainder to calculate the remainder, else we take the remainder with us down and shift left by 1 index position and append the next LSB of the divisor then we repeat the process.
Let's walk through an example,
We take 10001 / 101 (17 / 5) and go through binary division bit-by-bit in figure 1.0.
- A: is dividend10001 (17)
- B: is divisor 101 (5)
| Step | Bring down bit | Remainder before | Compare (≥ divisor?) | Quotient bit | Remainder after |
|---|---|---|---|---|---|
| 0 | 1 | 0 | 1 ≥ 101? no | 0 | 1 |
| 1 | 0 | 10 | 11 ≥ 101? no | 0 | 11 |
| 2 | 0 | 100 | 100 ≥ 101? no | 0 | 100 |
| 3 | 0 | 1000 | 1000 ≥ 101? yes → 1000 − 101 | 1 | 11 |
| 4 | 1 | 111 | 111 ≥ 101? yes → 111 − 101 | 1 | 10 |
As discussed above you can see that subtraction is conditional. It's only used when the divisor fits into the current remainder. Otherwise, you carry on shifting the dividend down by one position.
If you're not familiar with binary subtraction check out binary part-II where I'll walk you through binary subtraction bit-by-bit, then you’ll be able to do row 3 and 4 yourself (if you aren’t already).
Well that was binary long division, division closes out this binary series.
You now have add, subtract, multiply, and divide at the bit level. With these, you’ve built the full arithmetic core of a CPU.
If you want to stay updated follow me on X/Twitter.
Want to see coded examples? Click ALU a 32-bit Arithmetic Logic Unit that goes from integers to bit-by-bit simulations through logic gates, supports ADD, SUB, MULTIPLY, DIV.
Till next time.