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

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 
}

Solution 1:

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.

Solution 2:

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.

Solution 3:

The following answer was unashamedly lifted directly from Bit Twiddling Hacks By Sean Eron Anderson, [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.

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.

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

valter

Solution 5:

To generalise @TypelA'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);
}