# 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

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:

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

Scroll to Top