assembly - Perform integer division using multiplication

Looking at x86 assembly produced by a compiler, I noticed that
(unsigned) integer divisions are sometimes implemented as integer multiplications. These
optimizations seem to follow the
form

value / n => (value *
            ((0xFFFFFFFF / n) + 1)) /
            0x100000000

For
example, performing a division by
9:

12345678 / 9 =
            (12345678 * 0x1C71C71D) /
            0x100000000

A division
by 3 would use multiplication with 0x55555555 + 1, and so
on.

Exploiting the fact that the
mul instruction stores the high part of the result in the
edx register, the final result of the division can be obtained
using a single multiplication with a magic value. (Though this optimization is sometimes
used in conjunction with a bit-wise shift at the
end.)

I would like some insight on how this
actually works. When is this approach valid? Why must 1 be added to our "magic
number"?

Answer

That method is called, "Division by Invariant
Multiplication".

The constants that
you're seeing are actually approximates of the
reciprocal.

So rather than
computing:

N / D =
            Q

you do something
like this instead:

N *
            (1/D) = Q

where
1/D is a reciprocal that can be
precomputed.

Fundamentally, reciprocals are
imprecise unless D is a power-of-two. So there will some
round-off error involved. The +1 that you see is there to
correct for the round-off error.

/>

The most common example is division by
3:

N / 3 = (N *
            0xaaaaaaab) >>
            33

Where
0xaaaaaaab = 2^33 / 3 +
1.

This approach will generalize to
other divisors.