Swap bits — Visual explanation

Code that takes as input an integer (x) and swaps the bits at indices (i) and (j).

Following code is from EPI 4.2

def swap_bits(x, i, j):     
    if (x >> i) & 1 != (x >> j) & 1:         
    
    # ith and jth bits differ. 
    # We will swap them by flipping their values         
    # Select the bits to flip with bit mask.          
    # Since x^1 = 0 when x = 1 and 1 when x = 0 we can perform 
    # flip XOR         
    
    bit_mask = (1 << i) | (1 << j)         
    x ^= bit_mask     
    return x

Visual Explanation — Step by Step

1. Most Significant bit and Least Significant bit of the integer (x)

In this problem x = 73. The bits to be swapped are at positions 6 and 1. So i = 6 and j = 1.

2. Move the relevant bit at index i to the LSB position.

x >> i

3. Perform a bit AND operation to extract the bit value. In this case it gives 1.

(x >> i) & 1

4. Move the relevant bit at index j to the LSB position.

x >> j

5. Perform a bit AND operation to extract the bit value. In this case it gives 0.

(x >> j) & 1

6. At this point it is clear that the two bits to be swapped are different. Hence they need to be interchanged. If the bits were same we would simply return (x).

(x >> i) & 1 != (x >> j) & 1

7. Bit mask — Use a bit mask to mark the position of the indices.

(i << i) | (i << j)

7–1. Mark the first index position i with 1

(i << i)

7–2. Mark the second index position j with 1

(i << j)

7–3. Perform a bitwise OR to mark both the index positions in the bitmask

(i << i) | (i << j)

8. Toggle the bits to perform the swap operation. Use the bitmask with the index positions marked and perform bitwise XOR. Return the result.

x ^= bit_mask ( XOR to toggle the bits )

© vidyabhandary.github.io