Computing the Parity of a Word (Part 1)

30 Nov 2019 | 9 minutes to read

This is my study note of the book “Elements of Programming Interviews in Python” and Part 1 of the series.

What is a Parity?

Parity is a check that we use in communications systems. Unlike humans, computers won’t know if the data sent/received is valid or not. Parity (or parity bit check) is a simple method to quickly identify if the data received is valid from the source.

The par in parity means equality (or equivalence). As the naming suggests, we would like to check if the number of 1’s and 0’s are both ODD or EVEN. In this post, we will only consider ODD parity.

Let’s consider that packets (data) are sent in chunks of 1 bytes (= 8 bits). Among these 8 bits, we use 7 bits to contain the message and 1 bit to pass parity bit.

Here is the example of the data that we wish to send

|1|0|0|0|1|0|0| |

Since there are even number of 1’s in the message, we in order to validate against odd parity check, our parity bit needs to be 1.

|1|0|0|0|1|0|0|1|

If received data is altered as following, the reciever can tell that the data is invalid and ask to re-send the same data over. (Now, the number of 1’s are EVEN)

Sent:       |1|0|0|0|1|0|0|1|
Received:   |1|0|1|0|1|0|0|1|

However, this error detection won’t work all the time. Notice the case when two bits are altered:

Sent:       |1|0|0|0|1|0|0|1|
Received:   |1|0|1|0|0|0|0|1|

In here, received data is altered yet we still see odd number of 1’s -> Parity check says the data received is valid. Therefore, parity bit can fail to identify error.

Problem

So the problem we wish to solve is how to compute the parity of the received data? and how would you compute the parity of a very large number of 64-bit words?

In simpler question, we wish to come up with a solution that returns 1 if number of 1’s in the word is odd; otherwise, returns 0.

For example:

parity(1011) -> 1
parity(10001000) -> 0

Solution

Background

Before going into solutions, here we outline some background information that is required to answer the problem.

Bitwise Operations

AND
- A bitwise AND opeartion performs the logical AND opertation where it results a value of true if and only if both of its operands are true. In binary, the following truth table holds for 0 and 1. In python, we denote AND with &.
```
  0 & 0 == 0
  0 & 1 == 0
  1 & 0 == 0
  1 & 1 == 1
```
XOR
- A bitwise XOR operation performs the logical exclusive OR operation where is results a value of true when inputs differ. (One is true and other is false). In python, we denote XOR with ^.
```
  0 ^ 0 = 1
  0 ^ 1 = 0
  1 ^ 0 = 0
  1 ^ 1 = 1
```
Logical Shift
- A logical shift is a bitwise operation that shifts all the bits of its operand and zeros are filled on discarded bits. There are two shifts: left shift and right shift.
- Left shift (<< in python)
```
  23 << 1 == 46  # 00010111 << 1 == 00101110
```
- Right shift (>> in python)
```
  23 >> 1 == 11  # 00010111 >> 1 == 00001011
```

Solution 1: Brute-Force Algorithm

Let’s start with the simplest algorithm. Starting from Least Significant Bit (LSB), let’s check how many 1’s are there. We can keep track of a counter variable and increment it whenever we see a 1 and perform mod 2 after the scanning to return the answer. For example, given 1011 we have 3 1’s. Therefore our answer is 1 (== 3 % 2).

Now the question is: How can we take LSB from the word? To answer this, we will use a technique called bit masking.

Bit Masking

Using a bit mask, we can turn on/off desired bits in a word. There are two methods of bit masking: 1) Masking bits to 1 and 2) Masking bits to 0. We will consider the second case here. Masking bits to 0 utilizes characteristic of AND operation. Simply, we perform operation against same length word with 1’s in the positions where we want to turn on the bit and 0’s in the positions where we want to ignore it. Let’s look at the followig example.

From a given string 10010101, we wish to mask the upper four bits (ie. 1001). So let’s take AND operation against 00001111.

    10010101
AND 00001111
  = 00000101

After the AND operation, we got our desired masked value: 00000101.

Let’s come back to our algorithm. Here, we are only interested with the LSB of the word. Hence we can perform AND operation with 00000001 or simply 1. Since we have all the building blocks, let’s start implementing the algorithm.

def parity(x):
    counter = 0
    while x > 0:
        lsb = x & 1
        if lsb == 1:
            counter += 1
        
        # we perform right shift here to read in next bit data
        x = x >> 1
    result = counter % 2
    return result

Let’s improve our solution here. Take a look at the following table:

Counter	mod 2	result
0	0	0
1	1	1
2	0	0
3	1	1
4	0	0

Since we are only interesed with returning boolean output (0 or 1), we can actually replace counter % 2 with XOR operation.

def parity(x):
    result = 0
    while x > 0:
        lsb = x & 1
        result = result ^ lsb
        x = x >> 1
    return result

Or in more compact version, the solution looks like this:

def parity(x):
    result = 0
    while x:
        result ^= x & 1
        x >>= 1
    return result

This algorithm has time complexity of O(n), where n is the length of the word. This algorithm would work for small words, but it will get slower as the word size increases. Let’s take a look how we can improve it from here.

Solution 2: O(k) Solution (k is number of 1’s in the word)

Let’s go back to the definition of the parity, and see that we are only interested with the number of 1s.

The parity of a binary word is 1 is the number of 1s in the word is odd; otherwise it is 0.

Here we will utilize the following trick and idea of looking at only the active bits (ie. 1) to improve the performance of the algorithm.

Bit-fiddling Trick

Erasing the lowest set bit

x & (x-1) equals x with lowest set bit erased.

For example,

    x       00101100
    x-1     00101011
& --------------------
            00101000

Using this trick, we can reduce the time complexity of the algorithm to O(k) where k is the number of 1’s in a particular word.

def parity(x):
    result = 0
    while x:
        result ^= 1
        x &= (x-1)
    return result

This would have a same time complexity as Solution 1 for the worst case, but for average and best cases, this would perform much faster.

(Bonus) Other Bit-fiddling Trick

Isolating the lowest bit that is 1 in x x & ~(x-1) equals isolating the lowest bit that is 1 in x.

For example,

    x       00101100
  ~(x-1)    11010100
& --------------------
            00000100

Resources

Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash. Elements of Programming Interviews in Python: The Insider’s Guide., USA, 2016.
Great video introducing what parity bit is: https://www.youtube.com/watch?v=pUBdJi6eVYA

Dev Blog