Hacker's Delight

10-8. Unsigned Division

Unsigned division by a power of 2 is of course implemented by a single shift right logical instruction, and remainder by and immediate.

It might seem that handling other divisors will be simple: Just use the results for signed division with d > 0, omitting the two instructions that add 1 if the quotient is negative. We will see, however, that some of the details are actually more complicated in the case of unsigned division.

Unsigned Divide by 3

For a non-power of 2, let us first consider unsigned division by 3 on a 32-bit machine. Because the dividend n can now be as large as 2³² − 1, the multiplier (2³² + 2)/3 is inadequate, because the error term 2n/3 · 2³² (see “divide by 3” example above) can exceed 1/3. However, ...