c - 奇数ビットのビットパリティ コード

Question

ビットパリティを見つけるための調査中にこのコードに出くわしましたが、なぜこれが機能するのかほとんどわかりません。誰かがそのアルゴリズムについて教えてくれますか?

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

x &= 1;

Answer 1

The first line XORs the high 16 bits into the low 16 bits.

The second line XORs the the high half of the low 16 bits into the low half.

etc.

Before the last line, the low bit contains the parity of the initial 32 bits but the other bits contain intermediate results (garbage). The last line clears all of the garbage bits.

Each line takes half of the remaining values and XORs it into the other half. In total, because the XOR operation is associative and commutative, this works out the same as individually XORing each bit together.