How can I check if a value has even parity of bits or odd?

Question

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, 0110 has even parity, and 1110 has odd parity.

I have to return 1 if x has even parity.

int has_even_parity(unsigned int x) {
    return
}

Answer 1

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

Now x is 1100. The operation of x & ( x - 1 ), i.e., 1100 & 1011 is 1000. Notice that the original x is 1101 and after two operations of x & (x - 1) the x is 1000, i.e., two set bits are removed after two operations. If after an odd number of operations, the x becomes zero, then it's an odd parity, else it's an even parity.

Answer 2

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:

.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 64-bit C program compiled using MSVC. You can obviously port it to 32 bit or other compilers.

This has the advantage of being much faster than using C and it also leverages the CPU's functionality.

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

Answer 3

To generalise TypeIA's answer for any architecture:

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

Answer 4

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

Answer 5

GCC has built-in functions for this:

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.

and similar functions for unsigned long and unsigned long long.

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

These should 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.

Answer 6

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.

---

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 a through h. If we look at our number we see:

( 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, ab means the bit has the value a xor b).

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

The result is the following bits:

( a b c d ae bf cg dh )

---

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

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

The result is the following bits:

( 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:

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

The result is the following bits:

( 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).

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.

Answer 7

Here's a one line #define that does the trick for 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 #define speeds 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.

Admittedly, the same efficiencies may be obtained by using the inline function 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.

Answer 8

The following answer was unashamedly lifted directly from Bit Twiddling Hacks By Sean Eron Anderson, seander@cs.stanford.edu

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.

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.

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.

Answer 9

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