c - Bit hacking and modulo operation -

while reading this: http://graphics.stanford.edu/~seander/bithacks.html#reversebytewith64bitsdiv

i came phrase:

the last step, involves modulus division 2^10 - 1, has effect of merging each set of 10 bits (from positions 0-9, 10-19, 20-29, ...) in 64-bit value.

(it reversing bits in number)...

so did calculations:

reverted = (input * 0x0202020202ull & 0x010884422010ull) % 1023;  b = 74          :                                 01001010 b   * 0x0202020202 :       1000000010000000100000001000000010    = 9494949494 :01001010010010100100101001001010010010100   & 10884422010 :10000100010000100010000100010000000010000      = 84000010  :         10000100000000000000000000010000   % 1023        :                               1111111111     = 82        :                                 01010010 

now, part unclear part big number modulo 1023 (2^10 - 1) packs , gives me inverted bits... did not find doc relationship between bit operations , modulo operation (beside x % 2^n == x & (2^n - 1))) maybe if cast light on fruitful.

the modulo operation not give inverted bits per se, binning operation.

first line : word expansion

b * 0x0202020202 = 01001010 01001010 01001010 01001010 01001010 0

the multiplication operation has convolution property, means replicate input variable several times (5 here since it's 8-bit word).

first line : reversing bits

that's tricky part of hack. have remember working on 8-bit word : b = abcdefgh, [a-h] either 1 or 0.

b  * 0x0202020202 = abcdefghabcdefghabcdefghabcdefghabcdefgha     & 10884422010 = a0000f000b0000g000c0000h000d00000000e0000 

last line : word binning

modulo has peculiar property : 10 ≡ 1 (mod 9) 100 ≡ 10*10 ≡ 10*1 (mod 9) ≡ 1 (mod 9).

more generally, base b, b ≡ 1 (mod b - 1) number a ≡ sum(a_k*b^k) ≡ sum (a_k) (mod b - 1).

in example, base = 1024 (10 bits) so

b ≡ a0000f000b0000g000c0000h000d00000000e0000    ≡ a*base^4 + 0000f000b0*base^3 + 000g000c00*base^2 + 00h000d000*base +00000e0000    ≡ + 0000f000b0 + 000g000c00 + 00h000d000 + 00000e0000 (mod b - 1)   ≡  000000000a    + 0000f000b0     + 000g000c00     + 00h000d000     + 00000e0000 (mod b - 1)  ≡   00hgfedcba (mod b - 1) since there no carry (no overlap)