Computing modulus in parallel using bit manipulation

Question

The following link is to a bit hack that shows how to compute the modulus by 2^n - 1 in parallel: ModulusDivisionParallel

Can you explain how this bit manipulation works, and how to unroll the loop shown given a specific denominator (see example below, where do the bit masks come from)?

Example of unrolling the loop for 0xF:

y = x mod 0xF
y = x & 0x0F0F0F0F + ((x & 0xF0F0F0F0) >> 4)  
y = y & 0x00FF00FF + ((y & 0xFF00FF00) >> 8)  
y = y & 0x0000FFFF + ((y & 0xFFFF0000) >> 16)  
y = y & 0xF

Answer 1

First, a clarification:

When s = 4 (that is, the modulus is equal to 0xF) I get the following unrolling:

m = (n & 0x0F0F0F0F) + ((n >> 4) & 0x0F0F0F0F)
m = ((n >> 16) + (n & 0x0000FFFF)
m = ((n >>  8) + (n & 0x000000FF)
m = ((n >>  4) + (n & 0x0000000F)
m = ((n >>  4) + (n & 0x0000000F)
m = ((n >>  4) + (n & 0x0000000F)
m = ((n >>  4) + (n & 0x0000000F)
m = m == 0xF ? 0 : m;

This is very different than what you have in your question. To explain why this works:

Ever heard of the math trick where if you add up all the digits of a number and it's divisible by 9 then the original number is, too? That works because the remainders of dividing both the original and the sum by 9 is the same. Actually, that's what we're doing here, just in a different base -- in your example, with hexadecimal base.

The math kung-fu is this:

Each hexadecimal digit's contribution to the final value can be represented as V * 16 ^ P. Note that 16 ^ P = 1 (mod 15), so each hexadecimal digit's contribution to the final value is simply V (mod 15). In other words, to get the total contribution from all the digits, add them all up (mod 15).

The bitwise operations are just a clever way of doing this in logarithmic number of steps: repeatedly add the first half of the hexadecimal digits to the second half.

The problem with the 9's trick is you might end up with a two digit number: 99 = 9 + 9 = 18 (mod 10)! Then you just do the trick again: 18 = 1 + 8 = 9 (mod 10).

Likewise, we follow up with 'extra' iterations of m = ((n >> 4) + (n & 0x0000000F) until the remaining number is one digit.

Now the only remaining detail is if we get 0xF as the result in which case we want 0x0 instead.