How to find if there is a even or a odd number of "1" bit

Question

Is it possible to say if there is a even or a odd number of "1" bit in a binary representation of an int in C with a single test ? If no what is the fastest way to do it ?

Answer 1

One way to go about this is to count the number of bits and check the least-significant bit to see if the value is odd or even if it's 1 or 0 respectively. Given a 32-bit integer, we can count the number of 1s in its binary representation, Hamming Weight, through some clever bit manipulation. There's a good answer on find the Hamming Weight already here, and it also speaks on efficiency.

Take this algorithm of find the Hamming weight through sideway-accumulating addition. hasOddCount returns 1 if x has an odd number of 1s.

int hasOddCount(int x) {
    int first = 0x11 | (0x11 << 8);
    int second = first | (first << 16);
    int mask = 0xf | (0xf << 8);
    int count = 0;
    int sum = second & x;
    sum = (x>>1 & second) + sum;
    sum = (x>>2 & second) + sum;
    sum = (x>>3 & second) + sum;

    sum = sum + (sum >> 16);

    sum = ((sum & mask) + (mask & (sum >> 4)));
    count = (((sum >> 8) + sum) & 0x3f);

    //count is the Hamming weight, & by 0x1 to see if it's odd
    return count & 0x1;
}

Answer 2

Maybe not the fastest, but it works and is pretty simple:

int evenNumberOfOnes(unsigned int num)
{
    int n=0;
    while(num > 0) {
        n ^= num;
        num = num >> 1;
    }
    return n & 1;
}

Thanks to @EricPostpischil for tips about improvement.

Answer 3

I'm sure this is not the least possible code, but it's short and understandable;

#include <stdio.h>

int main(int argc, const char * argv[]) {
    unsigned x;
    int count;

    scanf("%u\n",&x);

    for(count=0;x;x>>=1)
        if(x&1)
            ++count;

    puts(count&1?"odd":"even");

    return(0);
}

BTW: I'm writing code with a .05 blood alcohol level, I didn't check this, and I might be embarrassed tomorrow if I got this simple task wrong. Please do not put this code into anything that operates thermonuclear weapons or driverless cars.

EDIT: After seeing other's answers which may also be correct &| tricky; The fastest code would really depend on architecture. Modulus is only super fast on some CPUs, on others it will eat a lot of cycles. Everything does shift in about the same few cycles.

Answer 4

int parity(int n) {
   int p = 0;

   for (;n;n>>=1) {
      p = (n&1) ? 1-p : p;
   }

   return p;
}

will return zero iff the number of 1's in argument n is even. Simple test:

#include <stdio.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>

int main() {
   srand(time(NULL));
   for (int i=0;i<100;i++) {   
      int n = rand();
      printf("%d has an %s number of 1's \n", n, parity(n)  ? "odd" : "even");
   }
}

Answer 5

I post this as a new answer since it's a bit hackish and a bit different from my other answer.

int evenNumberOfOnesFast(unsigned int num)
{
    unsigned char *b;
    b = (unsigned char *)#
    unsigned char par[4]={0};

    for(int i=0; i<8; i++) {
        for( int j=0; j<4; j++) {
            par[j]^=b[j];
            b[j]=b[j] >> 1;
        }
    }
    return (par[0] ^ par[1] ^ par[2] ^ par[3]) & 1;
}

Here, I assume that an int is 4 bytes. I hoped that this would enable the cpu to do some stuff in parallel in the pipeline. I'm not sure if that's the case, but this was about twice as fast as my previous version.

Here is the main function to test it:

#define N 10000000
int main()
{
    int * arr = malloc(N*sizeof(*arr));
    int * par = malloc(N*sizeof(*par));

    // Random values to prevent optimizer from just removing the code                                              
    srand(time(NULL));

    for(int i=0; i<N; i++)
        arr[i]=rand();

    // Correctness check                                                                                           
    for(int i=0; i<N; i++)
        if(evenNumberOfOnes(arr[i]) != evenNumberOfOnesFast(arr[i])) {
            perror ("Error");
            exit(EXIT_FAILURE);
        }

    clock_t begin, end;
    double time_spent;

    begin = clock();

    for(int i=0; i<N; i++)
        par[i]=evenNumberOfOnes(arr[i]);

    end = clock();
    time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
    printf(" Time: %f\n", time_spent);

    begin = clock();

    for(int i=0; i<N; i++)
        par[i]=evenNumberOfOnesFast(arr[i]);

    end = clock();
    time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
    printf(" Time: %f\n", time_spent);
}

And the result:

$ cc r.c -O3 -Wall -Wextra
$ ./a.out 
 Time: 0.201635
 Time: 0.093152

However, I also tested the solution hasOddCount that @Miket25 provided, and it is actually about ten times faster than my fast variant.