如何检查一个值的比特位是偶校验还是奇校验？

Question

如果一个值有偶数个'1'位，则其具有偶校验。如果一个值有奇数个'1'位，则其具有奇校验。例如，0110 具有偶校验，1110 具有奇校验。

如果 x 具有偶校验，则我必须返回 1。

int has_even_parity(unsigned int x) {
    return
}

- Manuel

---

可能是 Bit parity code for odd number of bits 的重复问题。 - Troyseph

请看这里：stackoverflow.com/questions/21589674/even-parity-of-a-unsigned-int。 - Troyseph

更一般（也更慢）的情况是 *在32位整数中计算设置位的数量*。 - Peter Mortensen

2010年的一个问题：*什么是通过位运算计算奇偶校验的最快方法？* - Peter Mortensen

Answer 1

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

假设您知道整数是32位的。

---

我们来看看这个是如何工作的。为了简单起见，让我们使用一个8位的整数，这样我们可以跳过前两个移位/XOR操作。我们将位标签为a到h。如果我们查看我们的数字，我们会看到：

( a b c d e f g h )

---

第一个操作是x ^= x >> 4（请记住，由于在本例中仅涉及8位整数，因此我们跳过前两个操作）。让我们通过组合XOR在一起的字母（例如，ab表示该位具有值a xor 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 )

结果是以下位：

( a ab abc abcd abcde abcdef abcdefg abcdefgh )

---

我们已经将原始字中所有位以最不重要位的形式XOR在一起。如果输入字中有偶数个1位（偶校验），则该位现在为零。同样的过程适用于32位整数（但需要我们在此演示中跳过的两个附加移位）。

代码的最后一行简单地剥离除了最不重要的位以外的所有位（& 1），然后翻转它（~x）。因此，结果为1，如果输入字的奇偶校验是偶数，则为0。

- TypeIA

---

代码的最后一行翻转了位，然后剥离了其他位（你的解释把这两个反过来了）。 - M.M

对于一个8位的值，只需要最后三个XOR行（而不是五个XOR行）吗？ - Peter Mortensen

Answer 2

GCC内置了内置函数来实现这个功能:

内置函数: int __builtin_parity (unsigned int x)

返回x的奇偶性，即x中1位数模2的余数。

对于unsigned long和unsigned long long，也有类似的函数。

即此函数的行为类似于has_odd_parity。 对于has_even_parity，请反转该值。

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

- Antti Haapala -- Слава Україні

---

不要在形状和大小上重新发明轮子，我认为这是最好的方法。 - faruk13

Answer 3

以下答案毫不掩饰地直接摘自Sean Eron Anderson（[e-mail]）的Bit Twiddling Hacks

使用乘法计算单词的奇偶性

以下方法仅使用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日提出了这个想法并将其发送给我。

- Troyseph

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;
}

- γηράσκω δ' αεί πολλά διδασκόμε

Answer 5

为了概括TypeIA的回答适用于任何体系结构：

int has_even_parity(unsigned int x) 
{
    unsigned char shift = 1;
    while (shift < (sizeof(x)*8))
    {
        x ^= (x >> shift);
        shift <<= 1;
    }
    return !(x & 0x1);
}

- HungryFoolish

---

这不是针对任何架构的。 - Antti Haapala -- Слава Україні

Answer 6

主要思想是：使用 x & ( x - 1 ) 取消最右边的 '1' 位。假设 x = 13(1101)，则 x & ( x - 1 ) 的操作为 1101 & 1100，结果为 1100，注意最右边的已设置的位被转换为 0。

现在，x 是 1100。再进行一次 x & ( x - 1 ) 操作，即 1100 & 1011，结果为 1000。注意原始的 x 是 1101，经过两次 x & (x - 1) 操作后，x 变成了 1000，也就是说，在两次操作后，有两个设置的位被移除了。如果经过奇数次操作之后，x 变成了零，则它是奇校验，否则它是偶校验。

- madhu sudhan

---

如果您需要更多的解释和代码，请使用以下链接：geeks for geeks link。 - madhu sudhan

Answer 7

这是一行用于 char 的#define代码。

#define PARITY(x) ((~(x ^= (x ^= (x ^= x >> 4) >> 2) >> 1)) & 1) /* even parity */

int main()
{
    char x=3;
    printf("parity = %d\n", PARITY(x));
}

它非常便携且易于修改以适应更大的单词（16、32位）。还要注意，使用#define可以加快代码速度，每个函数调用都需要时间来推动堆栈和分配内存。代码大小不会受到影响，特别是如果它只在您的代码中实现了几次-函数调用可能占用与XOR一样多的目标代码。

不可否认，通过使用此功能的内联函数版本，可以获得相同的效率，inline char parity(char x) {return PARITY(x);}（GCC）或__inline char parity(char x) {return PARITY(x);}（MSVC）。假设您保留了一行定义。

- Danny Holstein

---

这并不是严格正确的，它应该用于无符号字符，而不是有符号字符。 - Antti Haapala -- Слава Україні

哎呀，你说得对，谢谢。不过我不会修改这篇文章，对于使用它的人来说修复它将是微不足道的（或者不修复也可以）。 - Danny Holstein

Answer 8

int parity_check(unsigned x) {
    int parity = 0;
    while(x != 0) {
        parity ^= x;
        x >>= 1;
    }
    return (parity & 0x1);
}

- Shreyas Shivalkar

---

虽然这段代码可以回答问题，但是提供关于为什么和/或如何回答问题的额外背景信息有助于提高其长期价值。 - JAL

Answer 9

如果最终结果应该是一段可以与C程序一起工作（编译）的代码，那么我建议如下：

.code

; bool CheckParity(size_t Result)
    CheckParity PROC
    mov        rax, 0
    add        rcx, 0
    jnp        jmp_over
    mov        rax, 1
jmp_over:
    ret
CheckParity ENDP

END

这是我在64位C程序中使用的一段代码，用于检查计算结果的奇偶性，编译器使用MSVC。您可以将其移植到32位或其他编译器。

这种方法比使用C语言更快，并且利用了CPU的功能。

这个例子的作用是将一个参数作为输入（通过RCX - __fastcall调用约定传递）。它将其增加0，从而设置CPU的奇偶标志，然后将变量（RAX）设置为0或1，如果奇偶标志打开或关闭。

- papadp

---

我无法在Linux上使用GCC编译此代码（但是我对汇编知之甚少）。能否请您提供一个提示，告诉我如何将其嵌入到C程序中？ - étale-cohomology

x86 CPU计算奇偶校验位仅依据目标寄存器低字节中的位，而不是整个寄存器。 - Michael Petch

加上 add rcx,0 是更新标志位的不幸选择，只需要 test ecx,ecx 就足够了（因为奇偶校验标志位仅从8位计算，所以测试 rcx 的哪个部分并不重要，而 ecx 是短的机器码）。而 jnp 比没有跳转的 setp 更慢。通常大多数 C 编译器都会有内置的内部函数，这绝对是避免在3行代码中出现一些小错误的最佳（也是最快）选择...（就像这里演示的那样）。 - Ped7g

请参阅 https://dev59.com/16Hia4cB1Zd3GeqPWJuE#43929095，了解为什么即使您将其修复为适用于整个64位，这种方法仍然很糟糕，并且有更好的计算x86奇偶校验的方法。（附有Haswell基准测试） - Peter Cordes