1 minute read

Swap Bits - Elements of Programming Interviews (EPI)

Problem:

Given a 64 bit integer, Implement a function that swaps the bits at indices \(i\) and \(j\). As illustrated in this figure:

Solution:

The most naive solution would be to swap these bits the way we would swap values between normal variables through a temp variable. The naive solution will first extract the \(i^{th}\) and \(j^{th}\) bit by shifting and then assign to each bit with a mask.

If we were to notice that we only need to swap if the bits are different and bits can only really have 2 values, we dont really need to swap. All we need to do is flip the bits. If we wanted to flip the \(i^{th}\) bit then we simply XOR it with \(2^i\) which we can get with bit shifting 1 << i instead of using 2**i. So to flip the \(i^{th}\) bit of x just do x ^ (1 << i). To check if i and j bits are different we can do:

(x >> i) & 1) ^ (x >> j) & 1)

Which will return 1 if they are different and 0 if they are the same. Putting this all together we have this code:

def swap_bits(x, i, j):
    """Swap the ith bit of x with the jth bit of x"""
    if ((x >> i) & 1) ^ ((x >> j) & 1):  # checks if ith and jth bits of x are not same
        # x ^= 2**i  # inverts ith bit
        # x ^= 2**j  # inverts jth bit
        # Instead of computing 2**i we can do (1 << i) which is the same thing
        # and instead of doing 2 assignments we can prepare a bit mask
        # and then do a flip XOR with 1 assignment:
        bit_mask = (1 << i) | (1 << j)
        x ^= bit_mask
    return x