3 minute read

Parity and Bit Manipulation - Elements of Programming Interviews (EPI)

Problem:

Given a 64-bit integer, count the number of set bits.

Solution:

Counting Number of set bits can be done by either using the naive approach of simply bit shifting to the right by 1 and checking if the last bit is 1 or 0 or by using Peter Wegner’s method of removing the lowest set bit on each loop iteration by using subtraction. The naive approach will have the number of iterations equal to the bit of the highest set bit in the integer like a 32 bit int with only the 32 bit = 1 will take 32 loop iterations, while the wegner’s method has iterations equal to the number of set bits, it will take only 1 iteration for the 32 bit int with only the 32nd bit = 1.

def count_bits(x: int) -> int:
    """Naive Method"""
    num_bits = 0
    while x:
        num_bits += x & 1
        x >>= 1
    return num_bits


def count_bits(x: int) -> int:
    """Wegner's Method"""
    num_bits = 0
    while x:
        num_bits += 1
        x &= x - 1
    return num_bits

Another key bit-fiddling trick isolates the lowest bit that is 1 in x here ~ is the bitwise complement operator.

x & ~(x-1)

Problem:

Given a 64-bit integer implement a function to calculate its parity. The parity is the number of set bits mod 2.

Solution:

Calculating the Parity of an integer can be done in multiple ways. The parity is basically a flag which tells whether we have an even or odd number of set bits in an integer.

  • 1011 has parity 1
  • 1001 has parity 0.

The naive approach for parity will be simply using the bit counting method and instead of counting the number of bits we keep negating a parity flag. If we had to calculate the parity of an extremely large number of integers then we can use a lookup table with precalculated parities for integers (\(2^{64}\) integers will require exabytes of memory) and exploit the associativity of parity: the parity of (10100101) is parity(1010) and parity(0101). So we can divide the 64 bit integer into 4, 16 bit integers and simply lookup the parity of the 16 bit integers in our table (which will only require \(2^{16}\) bits of memory).

A further improvement on the lookup table can be by exploiting the XOR operator of the CPU and calculate parity in parallel(?). The parity of an integer is basically the XOR of the parity of its composing integers. These can be seen in code:

def parity(x: int) -> int:
    """ Function to compute parity"""
    # This is the slightly better approach than the brute force method, this uses the peter wegner method
    # a further improvement is to use Lookup Tables which has the parities of all 16 bit integers and
    # by using associativity of parity we can divide the 64 bit input into 4: 16 bit lookups, this is clearer if
    # we consider the example of parity if 8 bit int (11001010) is the same as calculating :
    # parity(1100) and parity(1010)
    # p = 0
    # while x:
          # p = ~p NOT WORKING since binary not of 0 goes to -1 (2s complement) and python has no unsigned ints (?)
    #     p ^= 1
    #     x &= x - 1
    # return p
    # This approach takes advantage of the XOR operation
    x ^= x >> 32
    x ^= x >> 16
    x ^= x >> 8
    x ^= x >> 4
    x ^= x >> 2
    x ^= x >> 1
    return x & 0x1

Variant: Write expressions that use bitwise operators, equality checks, and Boolean operators to do the following in O(1) time:

  • Right propagate the rightmost set bit in x, e.g., turns \((01010000)_2\) to \((01011111)_2\).
    • x | (x - 1)
  • Compute \(x\ mod\ n\) where n is a power of 2. e.g. returns 13 for 77 mod 64.
    • x & (n - 1)
  • Test if \(x\) is a power of 2 ,i.e.evaluates to true for x = 1, 2, 4, 8… False for all other values.
    • not bool(x & (x - 1)) solution 1
    • x == (x & ~(x - 1)) solution 2