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 matrix representation 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.
y = x ^ (x >> 1); y = y ^ (y >> 2); y = y ^ (y >> 4); y = y ^ (y >> 8); y = y ^ (y >> 16); More bit twiddling posts Popcount: counting 1s in a bit stream Inside the AES S-box Manipulating a random number generator.