bitParity checker - count how many 0's in a bit vector

Question

I was looking into bitwise operators and bit manipulation and stumbled upon this thread: bitParity - Finding odd number of bits in an integer

To summarize, the user asked for a function, int bitParity(int x), that returns 1 if there are an odd number of 0's in the two's complement representation of the integer passed in, otherwise, the function returns 0. All of this had to be done using only bitwise operators.

I am having no luck with trying to understand the accepted response and was hoping for some insight into it.

The solution:

x ^= x >> 16
x ^= x >> 8
x ^= x >> 4
x ^= x >> 2
x ^= x >> 1
x &= 1;

From what I think I can gather, the result of XOR between two same length, continuous sub bit vectors always has the same parity of 0's as the original bit vector. So by repeatedly applying the XOR operator on a bit vector and its shifted counter part until you reach a sub bit vector of length 1, you can chain the result to the entire original bit vector. Any correction to my thinking and further explanation would be appreciated.

I am confused as to how the right shift works to create "sub vectors" considering that it would be an arithmetic right shift since x is a signed value. I also do not understand why XOR between two sub bit vectors nets will have an odd number of 0's if and only if the original did.

score 2 · Accepted Answer · answered Jul 08 '20 at 11:03

The parity of a 32-bit value can be calculated by linking all bits together with

parity = bit0 ^ bit1 ^ bit2 ^ ... ^ bit31

In C this could be expressed as follows:

int parity = x & 1;      // Isolate least significant bit of x
parity ^= (x >> 1) & 1;  // Isolate second least significant bit of x
                         // and xor it together with the interim value

// Same for shift amounts from 2 up to 30 here

parity ^= (x >> 31) & 1;  // Isolate most significant bit of x
                         // and xor it together with the interim value

This would be 31 operations and that should be optimized here. For this purpose, individual bits are no longer isolated, but as many as possible at once: In the line

x ^= x >> 16

the following happens:

x before: | bit0         | bit1         |     | bit15
x >> 16:  | bit16,       | bit17,       | ... | bit31
----------+--------------+--------------+-----+-------------
x after:  | bit0 ^ bit16 | bit1 ^ bit17 | ... | bit15 ^ bit31

Bits 16 up to 31 of x remain unchanged, but they are not needed in the following. This leaves only half of all the bits that are now to be processed:

before: | bit0 ^ bit16                | ... | bit1 ^ bit23
>> 8 :  | bit8 ^ bit24                | ... | bit7 ^ bit31
--------+-----------------------------+-----+---------------------------
after:  | bit0 ^ bit8 ^ bit16 ^ bit32 | ... | bit1 ^ bit7 ^bit23 ^ bit31

Bits 8 up to 15 remain unchanged compared to the last step. It would be too confusing to write down the other three steps. At the end the value sought (the parity) is included in the least significant bit of x. The other bits are removed with

x &= 1;

bitParity checker - count how many 0's in a bit vector

1 Answers1