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

How to check if value has even parity of bits or odd?

提问by Manuel

A value has even parity if it has an even number of 1 bits. A value has an odd parity if it has an odd number of 1 bits. For example, 0110has even parity, and 1110has odd parity.

如果一个值具有偶数个 1 位，则它具有偶数奇偶性。如果一个值具有奇数个 1 位，则该值具有奇校验。例如，0110具有偶校验和1110奇校验。

I have to return 1if xhas even parity.

1如果x偶数平价，我必须返回。

int has_even_parity(unsigned int x) {
    return 
}

采纳答案by γηρ?σκω δ' αε? πολλ? διδασκ?με

Try:

尝试：

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

valter

瓦尔特

回答by TypeIA

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

Assuming you know ints are 32 bits.

假设您知道整数是 32 位。

---

---

Let's see how this works. To keep it simple, let's use an 8 bit integer, for which we can skip the first two shift/XORs. Let's label the bits athrough h. If we look at our number we see:

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

( abcdefgh)

( a b c d e f g h)

---

---

The first operation is x ^= x >> 4(remember we're skipping the first two operations since we're only dealing with an 8-bit integer in this example). Let's write the new values of each bit by combining the letters that are XOR'd together (for example, abmeans the bit has the value axor b).

第一个操作是x ^= x >> 4（记住我们跳过了前两个操作，因为在这个例子中我们只处理一个 8 位整数）。让我们通过将经过异或运算的字母组合在一起来编写每个位的新值（例如，ab表示该位的值是 axor b）。

( abcdefgh) xor ( 0000abcd)

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

The result is the following bits:

结果是以下位：

( abcdaebfcgdh)

( a b c d ae bf cg dh)

---

---

The next operation is x ^= x >> 2:

接下来的操作是x ^= x >> 2：

( abcdaebfcgdh) xor ( 0 0 abcdaebf)

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

The result is the following bits:

结果是以下位：

( abacbdacebdfacegbdfh)

( a b ac bd ace bdf aceg bdfh)

Notice how we are beginning to accumulate all the bits on the right-hand side.

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

---

---

The next operation is x ^= x >> 1:

接下来的操作是x ^= x >> 1：

( abacbdacebdfacegbdfh) xor ( 0 abacbdacebdfaceg)

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

The result is the following bits:

结果是以下位：

( aababcabcdabcdeabcdefabcdefgabcdefgh)

( a ab abc abcd abcde abcdef abcdefg abcdefgh)

---

---

We have accumulated all the bits in the original word, XOR'd together, in the least-significant bit. So this bit is now zero if and only if there were an even number of 1 bits in the input word (even parity). The same process works on 32-bit integers (but requires those two additional shifts that we skipped in this demonstration).

我们已将原始字中的所有位累加在一起，并在最低有效位中进行异或运算。因此，当且仅当输入字中存在偶数个 1 位（偶数奇偶校验）时，该位现在为零。相同的过程适用于 32 位整数（但需要我们在本演示中跳过的那两个额外的移位）。

The final line of code simply strips off all but the least-significant bit (& 1) and then flips it (~x). The result, then, is 1 if the parity of the input word was even, or zero otherwise.

最后一行代码简单地去除了除最低有效位 ( & 1) 之外的所有内容，然后将其翻转 ( ~x)。如果输入字的奇偶校验为偶数，则结果为 1，否则为 0。

回答by Troyseph

The following answer was unashamedly lifted directly from Bit Twiddling Hacks By Sean Eron Anderson, [email protected]

以下答案直接来自Sean Eron Anderson 的 Bit Twiddling Hacks，[email protected]

Compute parity of word with a multiply

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

The following method computes the parity of the 32-bit value in only 8 operations >using a multiply.

以下方法仅在 8 次运算中使用乘法计算 32 位值的奇偶校验。

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

Also for 64-bits, 8 operations are still enough.

同样对于 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 came up with this and sent it to me on Sept. 2, 2007.

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

回答by Antti Haapala

GCC has a built-in functionfor this:

GCC 有一个内置函数：

Built-in Function: int __builtin_parity (unsigned int x)

Returns the parity of x, i.e. the number of 1-bits in x modulo 2.

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

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

I.e. this function behaves like has_odd_parity. Invert the value for has_even_parity.

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

This is guaranteed to be the fastest alternative on GCC. Of course its use is not portable as such, but you can use it in your implementation, guarded by a macro for example.

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

回答by Rishav Ambasta

To generalise @TypelA's answer for any architecture:

概括@TypelA 对任何架构的回答：

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

回答by madhu sudhan

The main idea is this. Unset the rightmost '1' bit by using x & ( x - 1 ). Lets say x = 13(1101) and the operation of x & ( x - 1 )is 1101 & 1100which is 1100, notice that the rightmost set bit is converted to 0.

主要思想是这样的。使用 取消设置最右边的“1”位 x & ( x - 1 )。假设 x = 13(1101) 并且x & ( x - 1 )is的运算1101 & 1100是 1100，注意最右边的设置位被转换为0。

Now xis 1100. The operation of x & ( x - 1 )i.e 1100 & 1011is 1000. Notice that the original xis 1101and after two operations of x & (x - 1)the xis 1000, i.e two set bits are removed after two operations. If after oddnumber of operations, the xbecomes zero, then its a odd parity, else its a even parity.

现在x是1100。x & ( x - 1 )ie的操作1100 & 1011是1000。请注意，原来x是1101和两个操作之后x & (x - 1)的x是1000，即两组位被两个操作后取出。如果经过odd多次操作后，x变为零，则其为奇校验，否则为偶校验。

回答by Shreyas Shivalkar

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

回答by Danny Holstein

Here's a one line #definethat does the trick for a char:

这是一行#define可以解决 a 的问题char：

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

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

It's portable as heck and easily modified to work with bigger words (16, 32 bit). It's important to note also, using a #definespeeds the code up, each function call requires time to push the stack and allocate memory. Code size doesn't suffer, especially if it's implemented only a few times in your code - the function call might take up as much object code as the XORs.

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

Admittedly, the same efficiencies may be obtained by using the inlinefunction version of this, inline char parity(char x) {return PARITY(x);}(GCC) or __inline char parity(char x) {return PARITY(x);}(MSVC). Presuming you keep the one line define.

诚然，通过使用此函数的内联函数版本inline char parity(char x) {return PARITY(x);}(GCC) 或__inline char parity(char x) {return PARITY(x);}(MSVC)可以获得相同的效率。假设您保持一行定义。

回答by papadp

This is quite an old question but I'm posting this for whoever might use it in the future.

这是一个相当古老的问题，但我将其发布给将来可能使用它的人。

I won't add an example of doing it in c since there are enough good answers already.

我不会添加在 c 中执行此操作的示例，因为已经有足够好的答案。

In case the end result is supposed to be a piece of code that can work (be compiled) with a c program then I suggest the following:

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

.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

This is a piece of code I'm using to check the parity of calculated results in a 64bit c program compiled using MSVC. You can obviously port it to 32bit or other compilers.

这是我用来检查使用 MSVC 编译的 64 位 c 程序中计算结果的奇偶校验的一段代码。您显然可以将其移植到 32 位或其他编译器。

This has the advantage of being much faster than using c and it also leverages the cpus functionality.

这具有比使用 c 快得多的优点，并且还利用了 cpu 功能。

What this example does is take as input a parameter (passed in RCX - __fastcall calling convention). It increments it by 0 thus setting the cpus Parity Flag and then setting a variable (RAX) to 0 or 1 if Parity Flag is on or not.

此示例所做的是将参数作为输入（在 RCX 中传递 - __fastcall 调用约定）。它将它增加 0，从而设置 cpu 奇偶校验标志，然后如果奇偶校验标志打开与否，则将变量 (RAX) 设置为 0 或 1。