Dev Blog

Computing the Parity of a Word (Part 2)

02 Dec 2019 | 5 minutes to read

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

Solution 3: Lookup Table

Now, let’s consider a qualitatively different approach. The problem states that we wish to calculate parity up to 64 bit integer, which equals to 264 = very very large number!! One approach to calculate parity for a big binary word is to use an array-based lookup table. (This is a common performance improving technique in bit fiddling compuations.) Let’s start with defining what lookup table is.

Lookup Table

We can think of lookup table as something like a dictionary. So when we have a unique key (= word), we can easily look for its corresponding value (= definition). Let’s focus on array-based lookup table here. An array is a list of values with numeric index typically starting with 0.

Value: |"a"|"party"|"cup"|"pencil"|"plane"|
Index: | 0 |   1   |  2  |   3    |   4   |

So using the example above, let’s say that our array is called Array, then Array[0] returns "a", Array[2] returns “cup”, and similarly, Array[4] returns “plane”. (Note: that you cannot go beyond the index range that is not defined. ie. Array[5] is not accepted and it will return an error). The typical lookup operation’s runtime is O(1).

So can we create 264 lookup table entry and make our algorithm O(1)? Yes, but… this would require us a storage space of around two exabytes (or 20 million terabytes). Let’s go back to calculating parity for very small number.

The 1-bit case is the simplest form, where parity equals to the bit number itself.

parity(0) -> 0
parity(1) -> 1

Now, let us consider the 2-bit case.

parity(00) -> 0
parity(01) -> 1
parity(10) -> 1
parity(11) -> 0

Doesn’t this look like XOR truth table? We can also say that the parity of the 2-bit case equals to XOR operation between the first bit and the second bit. (parity == b0 ^ b1)

Can we extend this to the 3-bit case? Yes! The parity is equivalent to b0 ^ b1 ^ b2 == b0 ^ parity(b1b2).

parity(000) -> 0
parity(001) -> 1
parity(010) -> 1
parity(011) -> 0
parity(100) -> 1
parity(101) -> 0
parity(110) -> 0
parity(111) -> 1

Knowing this, we can state the following:

  • The parity of the single bit is itself (Base case)
  • The parity of the concatenation of bitstrings x and y is the XOR of the parity of x and the parity of y

Let’s verify this with computing parity of 11001010. Let’s assume we have a parity lookup table for 2-bit cases. Then, we can breakdown the binary word into pairs of two bits:

(11) (00) (10) (10)

Let’s lookup these bits against the lookup table:

(0) (0) (1) (1)

XORing these numbers gives 0^0^1^1 == 0, which equals to the parity of 11001010!

How can we extract these bits (or divide it into chunks)? (11) can be extracted by right shifting the number by 6 bits (ie. 11001010 >> 6 == 00000011). But, we cannot fetch the next two bits with simple shifting as before. Shifting to right by 4 bits returns 00001100, where it has unwanted (11). Here we can perform masking technique on lower two bits to extract these. (ie. we can perform & with 00000011 to extract (00)). Then similar approach can be performed to get other pairs. (right shifting by 4 and masking extracts (01) and masking original word returns (01)).

Let’s combine these ideas to calculate the parity of 64-bit words. We will use size 16-bit lookup table to calculate 64-bit words. 16 results 216 = 65536 entries and 16 evenly divides 64 into 4 chunks. The algorithm looks like the following.

def parity(x):
    MASK_SIZE = 16
    BIT_MASK = 0xFFFF (== 1111111111111111)
    return (PRECOMPUTED_PARITY[x >> (3 * MASK_SIZE)] ^
            PRECOMPUTED_PARITY[(x >> (2 * MASK_SIZE)) & BIT_MASK] ^
            PRECOMPUTED_PARITY[(x >> (MASK_SIZE)) & BIT_MASK] ^
            PRECOMPUTED_PARITY[x & BIT_MASK])

The time complexity is a function fo the size of the keys used to index the lookup table. Let L be the width of the words for which we used for creating lookup table values (ie. 16 for above), and n the word size. Since there are n/L terms, the time complexity is O(n/L).

Solution 4: XOR property of parity

As we mentioned previously, the parity of the word is equal to the XOR of parity of the sub-words. Thus, we can comeup with the following algorithm.

def parity(x):
    x ^= x >> 32
    x ^= x >> 16
    x ^= x >> 8
    x ^= x >> 4
    x ^= x >> 2
    x ^= x >> 1
    return x & 0x1

This algorithm has time complexity of O(log(n)), where n is the word size.

Conclusion

We have successfully came up with the algorithm to solve the parity problem. We started with the simplest approach of brute-force algorithm. Then we utilized some characteristics of bit characteristics and manipulation techniques to improve the algorithm.

Resources

  • Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash. Elements of Programming Interviews in Python: The Insider’s Guide., USA, 2016.

Related Posts