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