C parity test

Question:

I'm having trouble creating a function that returns 0 if the number of bits set in an unsigned char is even and 1 if it's odd

Answer:

This is a suitable task for bit operators:

#include <stdio.h>

int checkParity(unsigned char a) {
    int odd = 0;
    while( a ) {
        odd ^= a & 1;
        a >>= 1;
    }    
    return odd;
}

// teste, igual o do @user5978    
int main(void) {
    int i = 0;
    for (i=0; i<255;i++) {
        printf(" %d => %d\r\n",i,checkParity( i ) );
    }
    return 0;
}

See working on IDEONE .

Points of interest:

• while( a ) { When a is false (zero), the function is completed;

• odd ^= a & 1; Here we are doing an XOR between the variable odd and the last bit of a – in other words, if the bit is zero, nothing changes, if the bit is one, odd alternates between 0 and 1.

• a >>= 1; since we've already used the last bit of a , we shift all the bits to the right to repeat the process (the effect is the same as an integer division by two, except without the "mathematics" concern).

Basically, as the question asks for zero in the case of even bits, the logic is very simple: at each bit we "turn on" the variable odd , and on the next we turn it off. If the quantity is even, odd end in zero, if not, in one.

Eliminating a variable:

Once you understand the code above, it can be simplified by removing the odd variable:

int checkParity(unsigned char a) {
    while( a > 1 ) a = ( a >> 1 ) ^ ( a & 1 );
    return a;
}

It's the same logic, but we're working with the successive rotation of a and an XOR with its last bit.

See working on IDEONE .

Without loop solution:

This solution is "inspired" by @JJoao's post, which eliminates the need for looping , further optimizing the result. The technique is different, but the "bit brushing" philosophy for extreme optimization is similar.

I started from this link , which has some very interesting algorithms, with bit operation:

http://www.graphics.stanford.edu/~seander/bithacks.html

One of them fits like a glove if adapted to our case:

int checkParity(unsigned char a) {
    a ^= a >> 4;
    a &= 0xf;
    return ( 0x6996 >> a ) & 1;
}

I won't go into the details of the math of the thing, but "drawing" the bits on paper makes it easier to visualize the "move".

Simply put, as the parity is cyclic (with inversion), the value is simply merged to fit 4 bits, and the value 0x6996 is simply a "table" with the result for the 16 possible cases of the result. It is a pre-calculated value, to optimize the function.

See working on IDEONE