1 minute read

Reverse Bits - Elements of Programming Interviews (EPI)

Problem:

Write a program that takes a 64 bit unsigned integer and returns the 64 bit unsigned integer consisting of the bits of the input in reverse order. For example, if the input is (1110000000000001), the output should be (1000000000000111).

Solution:

The naive solution will be to loop over the first half 32 bits and Swap Bits with the corresponding mirror bit in the other half. e.g: swap bit 0 with bit 63, swap bit 1 with 62 and so on…

Instead of this we can take advantage of caching and split our 64-bit into 4 16-bit numbers A, B, C, D. We also prepare a lookup table called reversed where the number at index i is the reversed version of i. example:

  • reversed[24] = 6144 because
  • bin(24) = 0000000000011000 and
  • bin(6144) = 0001100000000000

So inorder to reverse our 64-bit integer which we can think of as A-B-C-D we need to form a new integer which looks like reversed[D]-reversed[C]-reversed[B]-reversed[A]. This can be very easily done by simply bit masking 16-bit portions and shifting them by a multiple of 16 and gluing them together with an OR. In code:

import swap_bits

def reversed_table() -> list:
    """Function to produce a list containing all 16bit integers along
    with their reversed versions"""
    result = []
    for i in range(2**16 - 1):
        tmp = i
        for j in range(8):
            tmp = swap_bits.swap_bits(tmp, j, 15 - j)
        result.append(tmp)
    return result


def reverse_bits(x: int) -> int:
    """Function to reverse a 64 bit int assuming existence of a lookup table called reversed"""
    # The bit mask to extract 16 bits
    # 0xFFFF = 1111111111111111 in binary.
    reversed = reversed_table() 
    bit_mask = 0xFFFF
    mask_size = 16
    A = x >> mask_size * 3 & bit_mask
    B = x >> mask_size * 2 & bit_mask
    C = x >> mask_size & bit_mask
    D = x & bit_mask
    result = reversed[D] << mask_size * 3 \
        | reversed[C] << mask_size * 2 \
        | reversed[B] << mask_size \
        | reversed[A]
    return result

The separate assignments to variables A, B, C, D are done to improve readability. We couldve clumped everything inside the return statement.