Hacker's Delight

5-2. Parity

The “parity” of a string refers to whether it contains an odd or an even number of 1-bits. The string has “odd parity” if it contains an odd number of 1-bits; otherwise, it has “even parity.”

Computing the Parity of a Word

Here we mean to produce a 1 if a word x has odd parity, and a 0 if it has even parity. This is the sum, modulo 2, of the bits of x—that is, the exclusive or of all the bits of x.

One way to compute this is to compute pop(x); the parity is the rightmost bit of the result. This is fine if you have the population count instruction, but if not, there are better ways than using the code for pop(x).

A rather direct method is to compute

where n is the word size, and then the parity of x is given by the rightmost bit ...