Parity test in C

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 is odd

Answer 1

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 a 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 a, odd alternates between 0 and 1.

• a >>= 1; as we already used the last bit of a, we move all bits to the right to repeat the process (the effect is the same as a split by two made with integer, only without worry "math").

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

Eliminating a variable:

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

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 a XOR with its last bit.

See working on IDEONE.

Solution without loop:

This solution is "inspired" in @Jjoao’s post, which eliminates the need for loop, optimizing even more the result. The technique is different, but the philosophy of "brushing bits" 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 falls like a glove adapted to our case:

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

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

Summarizing enough, as the parity is cyclic (with inversion), simply the value is merged to fit in 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

Answer 2

Simply decompose the number by making successive divisions by 2, and check the result of the division. Thus:

#include <stdio.h>


int check(unsigned char a) {

    int n = 0;

    while (a > 0) {

        if (a%2!=0) {
            n++;
        }

        a = a/2;

    }    
     return !(n%2==0);
}


int main()
{
   int i = 0;

    for (i=0; i<255;i++) {
        printf(" %d => %d\r\n",i,check(i));
    } 

}

Answer 3

Be it x composed of 8 bits x=(a b c d e f g h)

Parity(x) = xor( a b c d e f g h )

The xor operator in C is ^.

int check(unsigned char x) {

  x ^= x >> 4;        // x = abcdefgh xor 0000abcd = a b c d ae bf cg dh
  x ^= x >> 2;        // x = ... = a b ac bd ace bdf aceg bdfh
  x ^= x >> 1;        // x = ... = a ab abc abcd ... ... abcedfgh
                      // ou seja o bit menos significativo tem a informação pretendida
  return x & 1;       // retorna bit menos significativo (remove os outros bits)
}

(It’s not my invention: I vaguely remember reading something like this somewhere in a book)

Update: alerted by the precious comment of @Baco added a small correction (linked to compatibilization unsign char / int / op bit by bit); let’s see if it is this...