让我们首先从一个 2 位示例开始,以便您了解发生了什么。四种可能是:
ab a^b
-- ---
00 0
01 1
10 1
11 0
您可以看到,a^b (xor)
对于偶数个位给出 0,对于奇数给出 1。这也适用于 3 位值:
abc a^b^c
--- -----
000 0
001 1
010 1
011 0
100 1
101 0
110 0
111 1
第 3 行到第 6 行使用了相同的技巧,将所有 32 位合并为一个 4 位值。第 3 行与 合并b31-16
以b15-0
给出 16 位值,然后第 4 行将结果b15-b8
与b7-b0
合并,然后第 5 行将结果b7-b4
与合并b3-b0
。由于b31-b4
(每个异或操作的上半部分)没有被该操作清除,第 6 行通过清除它们来解决这个问题(并使用二进制0000...1111
清除除低 4 位之外的所有位)。
这里的合并是在分块模式下实现的。通过“分块”,我的意思是它将值减少块而不是单个位,这允许它有效地将值减小到 4 位大小(它可以这样做,因为 xor 操作既是关联的又是可交换的) . 另一种方法是对 nybbles 执行七次异或运算,而不是三个。或者,在复杂性分析术语中,O(log n) 而不是 O(n)。
假设你有值0xdeadbeef
,它是二进制的1101 1110 1010 1101 1011 1110 1110 1111
。合并是这样发生的:
value : 1101 1110 1010 1101 1011 1110 1110 1111
>> 16: 0000 0000 0000 0000 1101 1110 1010 1101
----------------------------------------------------
xor : .... .... .... .... 0110 0001 0100 0010
(与不相关的位,将来不会使用的位,保留为.
字符)。
对于完整的操作:
value : 1101 1110 1010 1101 1011 1110 1110 1111
>> 16: 0000 0000 0000 0000 1101 1110 1010 1101
----------------------------------------------------
xor : .... .... .... .... 0110 0001 0100 0010
>> 8: .... .... .... .... 0000 0000 0110 0011
----------------------------------------------------
xor : .... .... .... .... .... .... 0010 0001
>> 4: .... .... .... .... .... .... 0000 0010
----------------------------------------------------
xor : .... .... .... .... .... .... .... 0011
而且,查看0011
下表,我们看到它给出了偶校验(原始值中有 24 个 1 位)。仅更改原始值中的一位(任何位,我选择了最右边的位)将导致相反的情况:
value : 1101 1110 1010 1101 1011 1110 1110 1110
>> 16: 0000 0000 0000 0000 1101 1110 1010 1101
----------------------------------------------------
xor : .... .... .... .... 0110 0001 0100 0011
>> 8: .... .... .... .... 0000 0000 0110 0011
----------------------------------------------------
xor : .... .... .... .... .... .... 0010 0000
>> 4: .... .... .... .... .... .... 0000 0010
----------------------------------------------------
xor : .... .... .... .... .... .... .... 0010
0010
在下表中是奇校验。
唯一的“魔术”是0x6996
通过四位值移位的值以确保正确设置低位,然后该位用于确定奇偶校验。0x6996
使用(binary )的原因0110 1001 1001 0110
是因为二进制值的奇偶校验性质,如划线页所示:
Val Bnry #1bits parity (1=odd)
--- ---- ------ --------------
+------> 0x6996
|
0 0000 0 even (0)
1 0001 1 odd (1)
2 0010 1 odd (1)
3 0011 2 even (0)
4 0100 1 odd (1)
5 0101 2 even (0)
6 0110 2 even (0)
7 0111 3 odd (1)
8 1000 1 odd (1)
9 1001 2 even (0)
10 1010 2 even (0)
11 1011 3 odd (1)
12 1100 2 even (0)
13 1101 3 odd (1)
14 1110 3 odd (1)
15 1111 4 even (0)
请注意,没有必要进行最后的常数移位。你可以很容易地继续合并操作,直到你得到一个位,然后使用那个位:
bool parity (unsigned int x) {
x ^= x >> 16;
x ^= x >> 8;
x ^= x >> 4;
x ^= x >> 2;
x ^= x >> 1;
return x & 1;
}
但是,一旦有了 value 0...15
,将一个常数移位该值可能比两个额外的 shift-and-xor 操作更快。