生成奇偶校验查找表

Question

我从这个链接中读到了用于计算奇偶校验的bit reading：Bit Twiddling Hacks

为了计算奇偶校验，有一种查找方法，它为0到255之间的5行代码的整数生成奇偶校验表。

#define P2(n) n, n ^ 1, n ^ 1, n 
#define P4(n) P2(n), P2(n ^ 1), P2(n ^ 1), P2(n) 
#define P6(n) P4(n), P4(n ^ 1), P4(n ^ 1), P4(n) 
#define LOOK_UP P6(0), P6(1), P6(1), P6(0)

unsigned int table[256] = { LOOK_UP };

我检查了值P2(n)和P4(n)，它们计算0..15的奇偶校验。但我不理解这些代码行背后的直觉。这些行是如何计算0..255的奇偶校验的？我想知道这种递归方法背后的直觉和理论。提前谢谢。

Answer 1

对于P2，位的奇偶校验设置为1是微不足道的：

0b00 -> 0
0b01 -> 1
0b10 -> 1
0b11 -> 0

前置00不会改变奇偶校验，

但预置下一个01更改奇偶校验：

0b0100 -> 1 // 0 ^ 1
0b0101 -> 0 // 1 ^ 1
0b0110 -> 0 // 1 ^ 1
0b0111 -> 1 // 0 ^ 1

0b10..的奇偶校验与0b01..相同，并将随0b11..再次更改

n ^ 1允许交换机：

n | n ^ 1
--|--------
0 | 1
1 | 0

或者，可能选择了!n或具有相同表格的其他公式

希望你现在明白这个模式了。