While reading this: http://graphics.stanford.edu/~seander/bithacks.html#ReverseByteWith64BitsDiv
I came to the phrase:
The last step, which involves modulus division by 2^10 - 1, has the effect of merging together each set of 10 bits (from positions 0-9, 10-19, 20-29, ...) in the 64-bit value.
(it is about reversing the bits in a number)...
so I did some calculations:
reverted = (input * 0x0202020202ULL & 0x010884422010ULL) % 1023;
b = 74 : 01001010
b
* 0x0202020202 : 1000000010000000100000001000000010
= 9494949494 :01001010010010100100101001001010010010100
& 10884422010 :10000100010000100010000100010000000010000
= 84000010 : 10000100000000000000000000010000
% 1023 : 1111111111
= 82 : 01010010
Now, the only part which is somewhat unclear is the part where the big number modulo by 1023 (2^10 - 1) packs and gives me the inverted bits... I did not find any good doc about relationship between bit operations and the modulo operation (beside x % 2^n == x & (2^n - 1))
) so maybe if someone would cast a light on this it would be very fruitful.
The modulus operator is added in the arithmetic operators in C, and it works between two available operands. It divides the given numerator by the denominator to find a result. In simpler words, it produces a remainder for the integer division. Thus, the remainder is also always an integer number only.
The modulo operation (abbreviated “mod”, or “%” in many programming languages) is the remainder when dividing. For example, “5 mod 3 = 2” which means 2 is the remainder when you divide 5 by 3.
It works, but a modulo reduction involves a division, and divisions are expensive. Much more expensive than multiplications.
The modulo operation does not give you the inverted bits per se, it is just a binning operation.
b * 0x0202020202 = 01001010 01001010 01001010 01001010 01001010 0
The multiplication operation has a convolution property, which means it replicate the input variable several times (5 here since it's a 8-bit word).
That's the most tricky part of the hack. You have to remember that we are working on a 8-bit word : b = abcdefgh
, where [a-h] are either 1 or 0.
b * 0x0202020202 = abcdefghabcdefghabcdefghabcdefghabcdefgha
& 10884422010 = a0000f000b0000g000c0000h000d00000000e0000
Modulo has a peculiar property : 10 ≡ 1 (mod 9)
so 100 ≡ 10*10 ≡ 10*1 (mod 9) ≡ 1 (mod 9)
.
More generally, for a base b
, b ≡ 1 (mod b - 1)
so for all number a ≡ sum(a_k*b^k) ≡ sum (a_k) (mod b - 1)
.
In the example, base = 1024
(10 bits) so
b ≡ a0000f000b0000g000c0000h000d00000000e0000
≡ a*base^4 + 0000f000b0*base^3 + 000g000c00*base^2 + 00h000d000*base +00000e0000
≡ a + 0000f000b0 + 000g000c00 + 00h000d000 + 00000e0000 (mod b - 1)
≡ 000000000a
+ 0000f000b0
+ 000g000c00
+ 00h000d000
+ 00000e0000 (mod b - 1)
≡ 00hgfedcba (mod b - 1) since there is no carry (no overlap)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With