有点黑客攻击和模数操作

阅读本文时: http : //graphics.stanford.edu/~seander/bithacks.html#ReverseByteWith64BitsDiv

我来到这句话:

最后一步,涉及模数除以2 ^ 10 – 1,具有将64位的每组10位(从位置0-9,10-19,20-29,…)合并在一起的效果值。

(它是关于反转数字中的位)…

所以我做了一些计算:

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

现在,唯一有点不清楚的部分是1023(2 ^ 10 – 1)的大数量模块包装并给我反转位的部分……我没有找到关于位操作和位操作之间关系的任何好文档模运算(除了x % 2^n == x & (2^n - 1)) )所以也许如果有人对此进行说明,那将是非常有成效的。

模运算本身不会给出反转位,它只是一个分箱操作。

第一行:单词扩展

b * 0x0202020202 = 01001010 01001010 01001010 01001010 01001010 0

乘法运算具有卷积属性,这意味着它会多次复制输入变量(这里为5,因为它是一个8位字)。

第一行:反转位

这是黑客攻击中最棘手的部分。 你必须记住我们正在处理一个8位字: b = abcdefgh ,其中[ah]是1或0。

 b * 0x0202020202 = abcdefghabcdefghabcdefghabcdefghabcdefgha & 10884422010 = a0000f000b0000g000c0000h000d00000000e0000 

最后一行:单词分箱

Modulo具有一个独特的属性: 10 ≡ 1 (mod 9)所以100 ≡ 10*10 ≡ 10*1 (mod 9) ≡ 1 (mod 9)

更一般地,对于基数bb ≡ 1 (mod b - 1)因此对于所有数a ≡ sum(a_k*b^k) ≡ sum (a_k) (mod b - 1)

在示例中, base = 1024 (10位)

 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)