Skip to content

Latest commit

 

History

History
64 lines (56 loc) · 1.55 KB

swap_bits.md

File metadata and controls

64 lines (56 loc) · 1.55 KB
Raw

Swap Bits

Given a 64-bit integer, swap the bits at indices i and j.

Example

  • Let x = 1234 in decimal
  • Let i = 3
  • Let j = 7
1234 in binary viewed as an array of bits
MSB 9 8 7 6 5 4 3 2 1 LSB
1 0 0 1 1 0 1 0 0 1 0
Bits [3] and [7] (0 and 1) will be swapped
MSB 9 8 7 6 5 4 3 2 1 LSB
1 0 0 0 1 0 1 1 0 1 0

The swapped number in decimal = 1114

Solution

def swap_bits(x, i, j):
    bit_i = x >> i & 1
    bit_j = x >> j & 1
    if bit_i != bit_j:
        x ^= 1 << i
        x ^= 1 << j
    return x

Explanation

  1. Extract the i-th bit and j-th bit by shifting to the right
  2. If the swap is necessary, flip the bits to swap

Code Dissection

  1. Extract the i-th bit 
    bit_i = x >> i & 1
  2. Extract the j-th bit 
    bit_j = x >> j & 1
  3. Check if the swap is necessary, which is if the bits are not equal to each other 
    if bit_i != bit_j:
  4. Flip the i-th bit 
    x ^= 1 << i
  5. Flip the j-th bit 
    x ^= 1 << j
  6. Return the decimal number with the swapped bits 
    return x

Useful References