Fast way to know compute parity of bitvector

Question

I am working with bitvectors in C. My bitvectors are unsigned long long's. For a large number of vectors I need to know if the parity, i.e. the number of bits that are 1, is even or odd.

The exact value is not important, just the parity. I was wondering if there is anything faster than calculating the number of ones and checking. I tried to think of something, but couldn't find anything.

A short example of how I want this to work:

void checkIntersection(unsigned long long int setA, unsigned long long int setB){
    if(isEven(setA & setB)){
        //do something
    }
}

Answer 1

With divide and conquer technique:

uint64_t a = value;
a ^= (a >> 32);            // Fold the 32 MSB over the 32 LSB
a ^= (a >> 16);            // reducing the problem by 50%
a ^= (a >> 8);             // <-- this can be a good break even point
..
return lookup_table[a & 0xff];  // 16 or 256 entries are typically good
..

Folding procedure can be applied until the end:

a ^= (a >> 1);
return a & 1;

In IA the Parity flag can be directly retrieved after the reduction to 8 bits.

a ^= (a >> 4); makes another good point to stop dividing, since some processor architectures can provide parallel Look Up Tables uint8_t LUT[16] embedded into XXM (or NEON) registers. Or simply the potential cache misses of 256-entry LUT's can simply overweight the computational task of one extra round. It's naturally best to measure which LUT size is optimal in a given architecture.

This last table consists actually of 16 bits only and can be emulated with the sequence:

return ((TRUTH_TABLE_FOR_PARITY) >> (a & 15)) & 1;

where bit N of the magic constant above encodes the boolean value for Parity(N).