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++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
#include <iostream> #include <bitset> using namespace std; // Function to find parity of number x int findParity(int x) { // Hexadecimal to Binary conversion can be checked here // http://www.binaryhexconverter.com/hex-to-binary-converter // recursively divide the (32-bit) integer into two equal // halves and take their XOR until only 1 bit is left x = (x & 0x0000FFFF)^(x >> 16); x = (x & 0x000000FF)^(x >> 8); x = (x & 0x0000000F)^(x >> 4); x = (x & 0x00000003)^(x >> 2); x = (x & 0x00000001)^(x >> 1); // return the last bit return x & 1; } // Compute parity of a number using lookup table int main() { int x = 127; cout << x << " in binary is " << bitset<8>(x) << endl; if (findParity(x)) cout << x << " contains odd bits"; else cout << x << " contains even bits"; return 0; } |
Output:
127 in binary is 01111111
127 contains odd bits
Here’s optimized version of above solution that has less number of operations –
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#include <iostream> #include <bitset> using namespace std; // Function to find parity of number x int findParity(int x) { // recursively divide the (32-bit) integer into two equal // halves and take their XOR until only 1 bit is left x ^= x >> 16; x ^= x >> 8; x ^= x >> 4; x ^= x >> 2; x ^= x >> 1; // return the last bit return x & 1; } // Compute parity of a number using lookup table int main() { int x = 15; cout << x << " in binary is " << bitset<8>(x) << endl; if (findParity(x)) cout << x << " contains odd bits"; else cout << x << " contains even bits"; return 0; } |
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++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
#include <iostream> #include <bitset> using namespace std; // macros to generate the lookup table (at compile-time) #define P2(n) n, n^1, n^1, n #define P4(n) P2(n), P2(n^1), P2(n^1), P2(n) #define P6(n) P4(n), P4(n^1), P4(n^1), P4(n) #define FIND_PARITY P6(0), P6(1), P6(1), P6(0) // lookup-table to store the parity of each index of the table // The macro FIND_PARITY generates the table unsigned int lookup[256] = { FIND_PARITY }; // Function to find parity of x int findParity(int x) { // print lookup table (parity of integer i) // for (int i = 0; i < 256; i++) // cout << "Parity of " << i << " is " << lookup[i] << "\n"; // assuming 32-bit(4 byte) integer, break the integer into // 16-bit chunks and take their XOR x ^= x >> 16; // Again split 16-bit chunk into 8-bit chunks and take their XOR x ^= x >> 8; // Note mask used 0xff is 11111111 in binary return lookup[x & 0xff]; } // Compute parity of a number using lookup table int main() { int x = 17; cout << x << " in binary is " << bitset<8>(x) << endl; if (findParity(x)) cout << x << " contains odd bits"; else cout << x << " contains even bits"; return 0; } |
Output:
17 in binary is 00010001
17 contains even bits
References: https://graphics.stanford.edu/~seander/bithacks.html
(1 votes, average: 5.00 out of 5)
Loading...
Thanks for reading.
Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
Leave a Reply