Previously, we talked about multiplication and Bitwise Shift Left. It was quite fun to figure out how to do multiplication since basically all CPUs support it (all had to be figured out without direct help).
Division however, is not supported by all CPUs, most noted by the modern handheld console Gameboy Advance that required a lot of division, but had no support for it.
The C and C++ standard requires the division and modulo operators, meaning they must be emulated by the compiler if hardware doesn't provide them. That's where I got to learn how to do it. I did not figure this out. In fact, I used this division code to figure out multiplication (check it out in my previous blog entry).

There are two types of division, one being the normal signed division. The other one is the one I will talk about since it is less work. The unsigned division: Meaning both dividend and divisor must be positive values. If they are negative, they are treated as unsigned (very large positive numbers).

The result of a division yields a quotient and a remainder (two answers). Multiplying the resulting quotient by the original divisor, and then adding the resulting remainder, equals the original dividend.

Quotient = Dividend / Divisor
Modulus = Dividend % Divisor

(Where / is the divide operator and % is the modulo operator, both being the result of the single division)

Division can under no circumstances be allowed if the divisor is 0. This should immediately throw an exception. Division by 0 is simply forbidden. That is true for all math, not just binary.

If divisor is higher than dividend, then quotient is always 0, and the modulus (remainder) is dividend. Those are all the special conditions to deal with before actually doing the division.

 

Binary division is done with power-of-2 values. You can shift all the bits of a value right by 1 bit to unsigned-divide that value by 2 (denoted by the >> operator).

If we have a dividend value of 100 (1100100), and we want to divide it by 5 (101), we start off by getting the difference in bit positions between them. Subtracting the number of bits from dividend (which is 7) by divisor (which is 3), gets us 4 bits. If we scale 1 bit up with 4 bits, as in 2 to the power of 4, it will become 16. 16 times 5 equals 80.
We scale up the divisor by 16, making it 80. For every bit we have left, of this scaling (4 bits, 2 to the power of 4), if divisor is less or equal to dividend, turn the current scaling bit on in the quotient (starts off at 0) and subtract divisor from dividend (becoming the modulus).
Then shift the scale to the right by one bit (dividing it by 2), and do the same thing to divisor. And repeat these steps as long as the scale is not 0.

 

Let's do a test run:

dividend = 100, divisor = 5, scale = 1 << 4 bits (to the left) (16), quotient = 0.

divisor = (divisor << 4 bits (to the left)) = 80.

For as long as scale is not 0:
(
 Only if divisor is less or equal to dividend (true):
 (
 quotient = quotient + scale (becomes 16).
 dividend = dividend - divisor (100 - 80 = 20).
 )

 divisor = divisor >> 1 (becomes 40).
 scale = scale >> 1 (becomes 8).
)

For as long as scale is not 0:
(
 Only if divisor (40) is less or equal to dividend (20) (false):
 (
 quotient = quotient + scale.
 dividend = dividend - divisor.
 )

 divisor = divisor >> 1 (becomes 20).
 scale = scale >> 1 (becomes 4).
)

For as long as scale is not 0:
(
 Only if divisor (20) is less or equal to dividend (20) (true):
 (
 quotient = quotient + scale (becomes 20).
 dividend = dividend - divisor (20 - 20 = 0).
 )

 divisor = divisor >> 1 (becomes 20).
 scale = scale >> 1 (becomes 4).
)

For as long as scale is not 0:
(
 Only if divisor (20) is less or equal to dividend (0) (false):
 (
 quotient = quotient + scale.
 dividend = dividend - divisor.
 )

 divisor = divisor >> 1 (becomes 10).
 scale = scale >> 1 (becomes 2).
)

For as long as scale is not 0:
(
 Only if divisor (10) is less or equal to dividend (0) (false):
 (
 quotient = quotient + scale.
 dividend = dividend - divisor.
 )

 divisor = divisor >> 1 (becomes 5).
 scale = scale >> 1 (becomes 1).
)

For as long as scale is not 0:
(
 Only if divisor (5) is less or equal to dividend (0) (false):
 (
 quotient = quotient + scale.
 dividend = dividend - divisor.
 )

 divisor = divisor >> 1 (becomes 2).
 scale = scale >> 1 (becomes 0).
)

scale is now 0. The division is completed, and quotient (20) is our result as well as modulus being dividend (0).

 

Let's do another test run. This time we do 5555 / 5555:

dividend = 5555, divisor = 5555, scale = 1 << 0 bits (to the left) (1), quotient = 0.

divisor = (divisor << 0 bits (to the left)) = 5555.

For as long as scale (1) is not 0:
(
 Only if divisor is less or equal to dividend (true):
 (
 quotient = quotient + scale (becomes 1).
 dividend = dividend - divisor (5555 - 5555 = 0).
 )

 divisor = divisor >> 1 (becomes 2777).
 scale = scale >> 1 (becomes 0).
)

scale is now 0. The division is completed, and quotient (1) is our result as well as modulus being dividend (0).

 

Let's do another test run. This time we do 256 (100000000)/ 33 (100001):

First, we need the difference of bits between the top bits of dividend (9) and divisor (6): 9 - 3 = 3.

dividend = 256, divisor = 33, scale = 1 << 3 bits (to the left) (8), quotient = 0.

divisor = (divisor << 3 bits (to the left)) = 264.

For as long as scale (8) is not 0:
(
 Only if divisor (264) is less or equal to dividend (256) (false):
 (
 quotient = quotient + scale.
 dividend = dividend - divisor.
 )

 divisor = divisor >> 1 (becomes 132).
 scale = scale >> 1 (becomes 4).
)

For as long as scale is not 0:
(
 Only if divisor (132) is less or equal to dividend (256) (true):
 (
 quotient = quotient + scale (becomes 4).
 dividend = dividend - divisor (256 - 132 = 124).
 )

 divisor = divisor >> 1 (becomes 66).
 scale = scale >> 1 (becomes 2).
)

For as long as scale is not 0:
(
 Only if divisor (66 (1000010)) is less or equal to dividend (124) (true):
 (
 quotient = quotient + scale (becomes 6).
 dividend = dividend - divisor (124 - 66 = 58).
 )

 divisor = divisor >> 1 (becomes 33 (100001)).
 scale = scale >> 1 (becomes 1).
)

For as long as scale is not 0:
(
 Only if divisor (33 (100001)) is less or equal to dividend (58) (true):
 (
 quotient = quotient + scale (becomes 7).
 dividend = dividend - divisor (58 - 33 = 25).
 )

 divisor = divisor >> 1 (becomes 16 (10000)).
 scale = scale >> 1 (becomes 0).
)

scale is now 0. The division is completed, and quotient (7) is our result as well as modulus being dividend (25).

A simple check to see if this is correct: 33 * 7 + 25 should equal 256.

 

A signed divide requires us to negate the resulting quotient if the divisor's sign bit was not equal to the dividend's sign bit, as well as the modulus being negated if dividend's sign bit was turned on. The division must be done on the absolute (positive) values of dividend and divisor as the test runs demonstrate.

 

 

Why do we need the difference between the top bits of dividend and divisor? And why do we scale up the divisor with that number of bits? Sadly, I don't know.

 

Division is one of the slowest operations. Only Square Root is slower. Therefore it is better to multiply with fractions (reciprocal of the value) when using floating point even if it yields worse precision. For integer math, bit shifting to the right to divide by a power-of-2 value is much much faster. However, CPUs are smart and can find those cases for you most of the time, so the speed is the same. Division and Modulo are always needed, and eventually you just need to use them when there is no other way.

 

This is my 11,000 post on this forum!