bitParity checker - 计算位向量中有多少个 0

Question

我正在研究按位运算符和位操作，偶然发现了这个线程：bitParity - Finding odd number of bits in an integer

总结一下，用户要求一个函数，int bitParity(int x)，如果传入整数的二进制补码表示中有奇数个 0，则 returns 1，否则，函数 returns 0。所有这些都必须仅使用按位运算符来完成。

我在尝试理解已接受的回复时运气不佳，希望能对此有所了解。

解决方法：

x ^= x >> 16
x ^= x >> 8
x ^= x >> 4
x ^= x >> 2
x ^= x >> 1
x &= 1;

据我所知，两个相同长度的连续子位向量之间的异或结果始终与原始位向量具有相同的奇偶校验 0。因此，通过对位向量及其移位的计数器部分重复应用 XOR 运算符，直到到达长度为 1 的子位向量，您可以将结果链接到整个原始位向量。任何对我的想法的更正和进一步的解释将不胜感激。

考虑到这将是算术右移，我对右移如何创建“子向量”感到困惑，因为 x 是一个带符号的值。我也不明白 为什么 两个子位向量之间的 XOR 网络将有奇数个 0 当且仅当原始有时。

Answer 1

32 位值的奇偶校验可以通过将所有位链接在一起来计算

parity = bit0 ^ bit1 ^ bit2 ^ ... ^ bit31

在 C 中，这可以表示如下：

int parity = x & 1;      // Isolate least significant bit of x
parity ^= (x >> 1) & 1;  // Isolate second least significant bit of x
                         // and xor it together with the interim value

// Same for shift amounts from 2 up to 30 here

parity ^= (x >> 31) & 1;  // Isolate most significant bit of x
                         // and xor it together with the interim value

这将是 31 个操作，应在此处进行优化。为此，各个位不再是孤立的，而是一次尽可能多：在行

x ^= x >> 16

发生以下情况：

x before: | bit0         | bit1         |     | bit15
x >> 16:  | bit16,       | bit17,       | ... | bit31
----------+--------------+--------------+-----+-------------
x after:  | bit0 ^ bit16 | bit1 ^ bit17 | ... | bit15 ^ bit31

x的第16位到第31位保持不变，但下面不需要它们。这只剩下现在要处理的所有位的一半：

before: | bit0 ^ bit16                | ... | bit1 ^ bit23
>> 8 :  | bit8 ^ bit24                | ... | bit7 ^ bit31
--------+-----------------------------+-----+---------------------------
after:  | bit0 ^ bit8 ^ bit16 ^ bit32 | ... | bit1 ^ bit7 ^bit23 ^ bit31

与上一步相比，第 8 位到第 15 位保持不变。把其他三个步骤写下来太混乱了。最后，寻求的值（奇偶校验）包含在 x 的最低有效位中。其他位用

删除

x &= 1;

bitParity checker - 计算位向量中有多少个 0

bitParity checker - count how many 0's in a bit vector

c

bit-manipulation

bitwise-operators

bitwise-xor