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"?