位的安全和模操作 [英] Bit hacking and modulo operation
问题描述
阅读本:<一href=\"http://graphics.stanford.edu/~seander/bithacks.html#ReverseByteWith64BitsDiv\">http://graphics.stanford.edu/~seander/bithacks.html#ReverseByteWith64BitsDiv
我来到了那句话:
最后一步,其由2 ^ 10涉及模数除法 - 1,具有
每组10位合并在一起(从位置0-9的效果,
10-19,20-29,...)中的64位值。
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)...
所以我做了一些计算:
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))
),所以也许如果有人施放这一点光将是非常富有成效的。
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 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
b * 0x0202020202 = 01001010 01001010 01001010 01001010 01001010 0
乘法操作具有卷积特性,这意味着它复制输入变量几次(5在这里,因为它是一个8位字)。
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).
这就是黑客的最棘手的部分。你要记住,我们是在一个8位字工作: B = ABCDEFGH
,其中[A-H]是1或0
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
最后一行:字分级
模有特殊的属性: 10≡1(MOD 9)
所以 100≡10 * 10≡10 * 1(MOD 9)≡ 1(MOD 9)
。
更一般地,对于一个基地 B
, B≡1(MOD b - 1)
那么所有数字 A≡总和(a_k * b ^ K)≡总和(a_k)(MOD b - 1)
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)
.
在这个例子中,基地= 1024
(10位)等等。
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)
这篇关于位的安全和模操作的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!