C parity test

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

• Since we already use the last bit of a >>= 1; , we shift all the bits to the right to repeat the process (the effect is the same as a division by two made with integer, only without worry "mathematics").

Basically as the question asks for zero in case of even bits, the logic is very simple: every bit "bind" the variable a , and in the following we disconnect. If the quantity is even, odd will end in zero, otherwise, in one.

Deleting a variable:

Once the above code is understood, 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 is the same logic, but we are working with the successive rotation of odd and an XOR with its last bit.

See working at IDEONE .

Solution without loop :

This solution is "inspired" in @JJao's post, which eliminates the need for loop , further optimizing the result. The technique is different, but the philosophy of "brushing bits" for extreme optimization is similar.

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

  

link

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

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

I will not go into detail about the math of the thing, but "drawing" the bits on the paper makes it easier to visualize the "play".

In short, since parity is cyclic (with inversion), simply the value is merged to fit into 4 bits, and the a value 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 at IDEONE

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

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

}

Be 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 having read something like this somewhere in a book)

Update: warned by the precious comment of @Baco I added a small correction (linked to unsign compatibility char / int / op bit by bit); Let's see if this is ...