Parity

It turns out it’s not too complex. Even that 0x6996 makes sense, eventually. The key to parity computation is that it is basically a reduce(xor, bitstream), and xor is commutative. This means that you have to apply xor a bunch of times, between bits and other bits or outputs of previous xor operations. The order doesn’t matter, as long as every bit is xor’ed exactly once. Like +, for example.

Computing the parity of a bitstream is like computing its sum, except you use xor instead of +. That’s all.

The first three lines in the function are like folding the integer onto itself, like a sandwich. It makes more sense this way:

uint32_t
fold_three_times(uint32_t n) {
    uint16_t upper_half = (n >> 16) 0xffff;
    uint16_t lower_half = n & 0xffff;
    uint16_t xor16 = upper_half ^ lower_half;

    uint8_t upper_byte = (xor16 >> 8) & 0xff;
    uint8_t lower_byte = xor16 & 0xff;
    uint8_t xor8 = upper_byte ^ lower_byte;

    // Let's pretend that uint4_t is an existing type for half bytes
    uint4_t upper_nibble = (xor8 >> 4) & 0xf;
    uint4_t lower_nibble = xor8 & 0xf;
    uint4_t xor4 = upper_nibble ^ lower_nibble;

    return xor4;
}

That’s equivalent to the first four lines.

Now we have a 4-bit number, $n$, composed of all source bits xor’ed. We could continue folding down until we have 1 bit left. But at this point, there is an alternative. A 4-bit number can have 16 different values: you could build a lookup table for the parity of each of those values and just use that.

In C:

int
lookup_parity(uint32_t n) {
    const int lookup_table[] = {0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0};
    if (n > 15) {
        return -1;
    }
    return lookup_table[n];
}

Again, xor is commutative, so it doesn’t matter in which order the 1’s and 0’s of your intermediary $n$ are: the end result is the same bit. Yes, depending on how you fold you could get $n=3$ or $n=9$, but that doesn’t matter. They both have parity 0.

But look at that lookup table! That looks almost like a… binary number! What if you interpret 0110100110010110 as binary?

✻Gasp✻

It’s 0x6996!

That’s right, instead of creating a lookup table where every value takes up an entire integer, you compress it down so it takes up only one bit. Then your lookup table fits in one integer. Now you can shift the lookup table down so that the element you want ends up at the lowest significant bit (0x6996 >> n). Set all other bits to zero (x & 1) and you got the value!

And that’s how you compute parity.

Oh, right, extending to 64 bits. Almost forgot.

Well, at this point, that’s just one more fold:

static int
parity(uint64_t n) {
    n ^= (n >> 32);
    n ^= (n >> 16);
    n ^= (n >> 8);
    n ^= (n >> 4);
    n &= 0xf;
    return (0x6996 >> n) & 1;
}

Why not take advantage of a 64 bit lookup table, as well? 0x96696996, and do one less fold at the end? Because that would make your $n$ 8 bits, which means its range is 256 values. You’d need a 256 bit computer, not 64 bits. It looks logarithmic, but it’s subtle.

• Sean Eron Anderson for maintaining the bit twiddling page
• Matthew Hendry for the lookup table idea
• Ryan North for the illustration.