Compute Parity of a Number using Lookup Table

In this post, we will see how to compute parity of a number using lookup table. The parity refers to the number of 1’s in a given binary number.

 

Odd parity (encoded as 1) means there are an odd number of 1’s and even parity (encoded as 0) means that there are an even number of 1’s. Parity bits are often used as a crude means of error detection as digital data is transmitted and received.

 


 

Naive solution would be to calculate parity by checking each bit of given number n one by one. The time taken is proportional to the number of bits in the number. We can perform better by turning off the rightmost set bit of the number one by one and find the parity. The time it takes is proportional to the number of bits set. We have already discussed both solutions here. In this post, few other interesting solutions are discussed.
 

The idea is to calculate the parity of an integer by recursively dividing the (32-bit) integer into two equal halves and take their XOR until only 1 bit is left. Taking the XOR will cancel out set bits at same position in two halves and since parity will not be effected if we take out even set bits from it (why?), we successfully reduce the problem into half at each step.


For example, we initially split the 32-bit (4 byte) integer into two 16-bit chunks and take their XOR. Then we again split 16-bit chunk into 8-bit chunks and take their XOR. Then 8-bit chunks further get divided into 4-bits chunks and so on.. We continue this process until only 1 bit is left.

C++

Download   Run Code

Output:

127 in binary is 01111111
127 contains odd bits

 


 

Optimized version of above solution (less number of operations) –
 
 

C++

Download   Run Code

Output:

15 in binary is 00001111
15 contains even bits

 


 

Compute parity using a lookup table –

 

We can use a lookup table to find parity in constant time. An integer in C/C++ usually takes 4 bytes for storage. That means maximum number it can store is 232-1. A lookup table for all 232-1 integers will be infeasible (Not to forget, we have negative numbers too). The trick is to create an 8-bit (1 byte) version of the table, then iterate over each byte in the integer to be checked and summing the results of the table lookup.

1 byte with all its bits set is 255 in decimal (11111111 in binary) and all bits unset is 0 in decimal (00000000 in binary). So lookup table should be of size 256 (0-255).
 

In the solution below, we’re using the macros to generate the lookup table. The lookup table will be generated at compile time by preprocessor. The first and last few numbers of the sequence will be
{ 0, 1, 1, 0, 1, 0, . . . , 0, 1, 0, 1, 1, 0 }
as

Parity of 0 is 0
Parity of 1 is 1
Parity of 2 is 1
Parity of 3 is 0
Parity of 4 is 1
Parity of 5 is 0
. . .
. . .
Parity of 250 is 0
Parity of 251 is 1
Parity of 252 is 0
Parity of 253 is 1
Parity of 254 is 1
Parity of 255 is 0

 
Consider n = 1691315356 (binary 01100100110011110110110010011100),
 

1. Split the 32-bit integer into 16-bit chunks

0110010011001111 | 0110110010011100

 

2. Take their XOR

0110010011001111 ^
0110110010011100
~~~~~~~~~~~~~~~~
0000100001010011

 

3. Split the 16-bit result into 8-bit chunks

00001000 | 01010011

 

4. Take their XOR

00001000 ^
01010011
~~~~~~~~
01011011

 
Now, 01011011 is 91 in decimal and lookup[91] will return 1 (odd parity). In below solution, split and XOR operation happens in single expression for each chunk.

C++

Download   Run Code

Output:

17 in binary is 00010001
17 contains even bits

References: https://graphics.stanford.edu/~seander/bithacks.html
 

Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz