Vince's thoughts

Binary stepwise division is exactly like performing a division by hand, so let't remember how it works.

Say you want to divide 135 (dividend) by 12 (divisor). The operations you do are like :

• how many times does 12 fit in 13 ? Answer : 1. So 1) note "1" as the first digit of the answer and 2) subtract 1x12 from 13, that is 1, and bring the next digit from the original divident (5) next to the 1. In other words, you must now divide 15 by 12
• how many times does 12 fit in 15 ? Answer : 1 So 1) note "1" as the second digit of the answer and 2) subtract 1x12 from 15, that is 3, and there is nothing left to bring next to it. We're done.

So we have the quotient : 11 (the two 1's found at each previous step), and we have the remainder : 3 (found at the end of the last step).

In fact, if we were working in a universe of 3-digit numbers, we would write the divisor as 012, the divident as 135, the remainder as 003 and the quotient as 011. Where does the 0 before the 11 come from ? Well, it comes from a first step I skipped above, that should be written like :

• how many times does 12 fit in 1 ? Answer : 0. So 1) note "0" as the very first digit of the answer and 2) don't change anything to 1 but bring the next digit from the original divident (3) next to the 1. In other words, you must now divide 13 by 12

So we always have to perform as many steps as the width of our numbers, 3 in the above case. That's when we know we're done.

To implement that logic more easily, we'll use a buffer B to store the current number to be divided. Instead of starting with the first digit in the buffer, we start with an empty buffer (B=0) and an empty answer (A=0) and each step will first load the next digit in the buffer. So we'll rewrite the above operations as :

• load one more digit from the dividend (1) into the buffer : B=1. How many times does 12 fit in 1 ? Answer : 0. So note "0" as the 1st digit of A and leave 1 in B : B=1
• load one more digit from the dividend (3) into the buffer : B = 13. How many times does 12 fit in 13 ? Answer : 1. So note "1" as the 2nd digit of A and store the difference (1) in B : B=1
• load one more digit from the dividend (5) into the buffer : B = 15. How many times does 12 fit in 15 ? Answer : 1 So note "1" as the 3rd digit of A and store the difference (3) in B : B = 3

Quotient A=011, Remainder B = 003.

The steps now look exactly identical :

1. Load one more digit from the dividend into the buffer
2. See if the divisor fits into the buffer.
3. If so, note how many times it fits as the next digit of A and store the remainder into B. If not, note 0 as the next digit of A and leave B unchanged

OK. Now imagine we do the same with binary numbers on 8-digit (8-bit) : We want to divide 10000111 (=135 in decimal) by 1100 (=12 in decimal) . The operations we do are : Start with B = 0 and A = 0.

1. load one more digit from the dividend (1) into the buffer : B = 1. How many times does 1100 fit in 1 ? Answer : 0. So note "0" as the 1st digit of A and leave 1 in B : B = 1.
2. load one more digit from the dividend (0) into the buffer : B = 10. How many times does 1100 fit in 10 ? Answer : 0. So note "0" as the 2nd digit of A and leave 10 in B : B = 10.
3. load one more digit from the dividend (0) into the buffer : B = 100. How many times does 1100 fit in 100 ? Answer : 0. So note "0" as the 3rd digit of A and leave 100 in B : B = 100.
4. load one more digit from the dividend (0) into the buffer : B = 1000. How many times does 1100 fit in 1000 ? Answer : 0. So note "0" as the 4th digit of A and leave 1000 in B : B = 1000.
5. load one more digit from the dividend (0) into the buffer : B = 10000. How many times does 1100 fit in 10000 ? Answer : 1 (take care, we're in binary. In binary it can just be 0 or 1 in any case). So note "1" as the 5th digit of A and store the difference (100) into B : B = 100.
6. load one more digit from the dividend (1) into the buffer : B = 1001. How many times does 1100 fit in 1001 ? Answer : 0. So note "0" as the 6th digit of A and leave 1001 in B : B = 1001.
7. load one more digit from the dividend (1) into the buffer : B = 10011. How many times does 1100 fit in 10011 ? Answer : 1. So note "1" as the 7th digit of A and store the difference (111) into B : B = 111.
8. load one more digit from the dividend (1) into the buffer : B =1111. How many times does 1100 fit in 1111 ? Answer : 1. So note "1" as the 8th digit of A and store the difference (11) into B : B : 11.

Quotient : A=00001011 (=11 in decimal). Remainder B = 11 (=3 in decimal).

Good news is : we have the same correct answer in binary.

Summary : to perform a binary stepwise division on <n> bits, we just have to perform the same operation <n> times, the operation being formalized as :

1. Load one more digit from the dividend into the buffer
2. Compare the current "buffer" with the divisor and see if it fits
3. If so, note 1 as the next digit of A and store the remainder into B. If not, note 0 as the next digit of A and leave B unchanged

A smart implementation in a CPU is to use a register R of 2x<n> bits, the lower half RL being loaded with the original dividend before starting and higher half RH being used as our B buffer. In our example, the 16-bit register R would start with 00000000 10000111 The step (1) then becomes a simple left shift by 1 of this register. (2) is a simple comparison : RH - divisor. According to the Carry (or Borrow) flag set by this comparison, we have two cases : (3a) if C is 0 (no borrow), set the next digit of A to 1 and set RH to RH - divisor. (3b) else set the next digit of A to 0 (no change to RH)

Smarter yet, each digit of A, as it is calculated, can be fed as the last digit of a register that would be shifted left by 1 at each turn. Wait, we just have such a register : that's RL. Each time it gets shifted left to feed RH, it leaves the last digit of RL free to be used as the next digit of A.

So in the end, we'll have the anwser A built bit by bit in RL, and the remainder in RH. Great !

If you're only interested in unsigned divisions, you can stop now. That's all there is to it.

In real life, however, we sometimes want to use signed numbers. In that case, the logic is similar, except that things like "fits in" and "compare" can take another meaning. So what this involves mainly is :

• a first step to set some flags according to signs of the dividend and divisor
• the same <n> operations we just described above (but taking into account the flags above to decide if it "fits")
• a few correction steps once the division is complete.