有点黑客攻击和模数操作

Question

阅读本文时: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)))所以也许如果有人会对此有所了解,那将是非常有成效的.

Answer 1

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

第一行:单词扩展

b*0x0202020202 = 01001010 01001010 01001010 01001010 01001010 0

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

第一行:反转位

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

b  * 0x0202020202 = abcdefghabcdefghabcdefghabcdefghabcdefgha
    & 10884422010 = a0000f000b0000g000c0000h000d00000000e0000

最后一行:单词binning

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)