如何检查值是否具有奇偶校验位或奇数？

Question

如果具有偶数1位,则值具有偶数奇偶校验.如果具有奇数1位,则该值具有奇校验.例如,0110具有偶校验,并1110具有奇校验.

1如果x有平价,我必须返回.

int has_even_parity(unsigned int x) {
    return 
}

Answer 1

x ^= x >> 16;
x ^= x >> 8;
x ^= x >> 4;
x ^= x >> 2;
x ^= x >> 1;
return (~x) & 1;

假设你知道int是32位.

让我们看看它是如何工作的.为了简单起见,让我们使用一个8位整数,我们可以跳过前两个移位/异或.让我们标记位a到h.如果我们查看我们的号码,我们会看到:

(a b c d e f g h)

第一个操作是x ^= x >> 4(记住我们正在跳过前两个操作,因为在这个例子中我们只处理一个8位整数).让我们通过组合被一起进行异或字母写入每个比特的新值(例如,AB指该位的值是一个异或b).

(a b c d e f g h)xor(0 0 0 0 a b c d)

结果如下:

(a b c d ae bf cg dh)

下一步是x ^= x >> 2:

(a b c d ae bf cg dh)xor(0 0 a b c d ae bf)

结果如下:

(a b ac bd ace bdf aceg bdfh)

注意我们如何开始累积右侧的所有位.

下一步是x ^= x >> 1:

(a b ac bd ace bdf aceg bdfh)xor(0 a b ac bd ace bdf aceg)

结果如下:

(一个 AB ABC ABCD ABCDE ABCDEF ABCDEFGH ABCDEFGH)

我们已经在最低有效位中累积了原始字中的所有位,XOR'd.因此,当且仅当输入字中存在偶数个1位(偶校验)时,该位现在为零.相同的过程适用于32位整数(但需要我们在本演示中跳过的那两个额外的移位).

最后一行代码简单地删除除了最不重要的位(& 1)之外的所有内容然后翻转它(~x).如果输入字的奇偶校验是偶数,则结果为1,否则为零.

Answer 2

GCC为此具有内置函数：

内置功能： int __builtin_parity (unsigned int x)

返回 的奇偶校验x，即 x 模 2 中 1 位的数量。

和类似的功能unsigned long和unsigned long long。

即这个函数的行为就像has_odd_parity. 反转 的值has_even_parity。

这些应该是 GCC 上最快的替代方案。当然，它的使用本身是不可移植的，但您可以在您的实现中使用它，例如由宏保护。

Answer 3

下面的答案是直接从Bit Twiddling Hacks中解脱出来的Sean Eron Anderson,seander @ cs.stanford.edu

用乘法计算单词的奇偶校验

以下方法仅使用乘法计算8个操作中的32位值的奇偶校验.

unsigned int v; // 32-bit word
v ^= v >> 1;
v ^= v >> 2;
v = (v & 0x11111111U) * 0x11111111U;
return (v >> 28) & 1;

同样对于64位,8个操作仍然足够.

unsigned long long v; // 64-bit word
v ^= v >> 1;
v ^= v >> 2;
v = (v & 0x1111111111111111UL) * 0x1111111111111111UL;
return (v >> 60) & 1;

Andrew Shapira想出了这个并于2007年9月2日把它寄给了我.

Answer 4

尝试：

int has_even_parity(unsigned int x){
    unsigned int count = 0, i, b = 1;

    for(i = 0; i < 32; i++){
        if( x & (b << i) ){count++;}
    }

    if( (count % 2) ){return 0;}

    return 1;
}

瓦尔特