The previous post mentioned adding a parity bit to a string of bits as a way of detecting errors. The parity of a binary word is 1 if the word contains an odd number of 1s and 0 if it contains an even number of ones.
Codes like the Hamming codes in the previous post can have multiple parity bits. In addition to the parity of a word, you might want to also look at the parity of a bit mask AND’d with the word. For example, the Hamming(7, 4) code presented at the end of that post has three parity bits. For a four-bit integer x
, the first parity bit is the parity bit of
x & 0b1011
the second is the parity bit of
x & 0b1101
and the third is the parity of
x & 0b1110
These three bit masks are the last three columns of the generator matrix for of the Hamming(7, 4) code:
1 0 0 0 1 1 1 0 1 0 0 0 1 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0
More generally, any linear operation on a vector of bits is given by multiplication by a binary matrix, where arithmetic is carried out mod 2. Matrix products can be defined in terms of inner products, and the inner product of words x
and y
is given by the parity of x&y
.
Given that parity is important to compute, how would you compute it?
If you have a popcount function, you could read the last bit of the popcount. Since popcount counts the number of ones, the parity of x
is 1 if popcount(x)
is odd and 0 otherwise.
gcc extensions
In the earlier post on popcount, we mentioned three functions that gcc provides to compute popcount:
__builtin_popcount __builtin_popcountl __builtin_popcountll
These three functions return popcount for an unsigned int
, an unsigned long
, and an unsigned long long
respectively.
In each case the function will call a function provided by the target processor if it is available, and will run its own code otherwise.
There are three extensions for computing parity that are completely analogous:
__builtin_parity __builtin_parityl __builtin_parityll
Stand-alone code
If you want your own code for computing parity, Hacker’s Delight gives the following for a 32-bit integer x
.
The last bit of y
is the parity of x
.
y = x ^ (x >> 1); y = y ^ (y >> 2); y = y ^ (y >> 4); y = y ^ (y >> 8); y = y ^ (y >> 16);
Something’s wrong with your example from Hacker’s Delight.
If I put “5” in to what you have written,
101
111
110
Six isn’t the right answer.
Compilers have slowly been incorporating a lot of these common algorithms to their optimizers…
https://godbolt.org/z/eNP4MJ
Note that “simple_bits” compiles down to the same code as the builtin without relying on non-standard compiler features while the hacker’s version hasn’t made it there. There’s a fun article by the owner of godbolt.org on ACM’s site about some of the craziness under the hood:
https://queue.acm.org/detail.cfm?id=3372264
Thanks. I had left out an important sentence that I just added: The last bit of
y
is the parity ofx
.