# Computing parity of a binary word

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);
```

## 2 thoughts on “Computing parity of a binary word”

1. Jeffrey McBeth

Something’s wrong with your example from Hacker’s Delight.
If I put “5” in to what you have written,
101
111
110

2. Thanks. I had left out an important sentence that I just added: The last bit of `y` is the parity of `x`.