Fast division by multiplication

You're trying to calculate n/d (and the result should be rounded off to the nearest integer[1]). Division is expensive, but you observe that you can divide by a power of 2 cheaply using a shift instruction, so you decide to transform the calculation into something of the form (n * d')/(2^N), which is a multiply and a shift-right instruction. For the two forms to be equivalent, d' = 2^N / d, which you precompute.

Certain values of N can be more convenient from a computational point of view - for example, multiplying 2 32-bit integers yields a 64-bit result; on most architectures, the high and low halves either land in separate 32-bit registers, or you have to calculate each half with a separate instruction. So if you choose N=32, you don't even need a shift instruction: you simply drop the low bits.

You also need to make sure you choose your d' such that your rounding will be correct for all values of n.

Depending on the exact value of d', it may also be possible to decompose the multiplication further, leaving only shifts and additions/subtractions.

[1] Of course, for floating-point numbers, you can just calculate 1/d, save it and multiply by it any time you need to divide by d.

Let's say that our integer domain is 0 to 9999 (decimal) but you have enough space to handle up to 9 digits. To integer-divide something by 3, you can multiply by 33334 and shift-right 5 digits (i.e. drop the last 5):

  7939 * 33334 = 264638626;
  2646 (right answer) after dropping 5 digits. 

For some divisors, we're better off. For example, if n = 25 and we're in base 10, you can multiply by 4 and drop 2 digits, as 4/100 = 1/25.

Same principle applies to binary.