阅读本文时: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)
.
更一般地说,对于一个基地b
,b ? 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)