CODEWITHSUNDEEP
algorithmbinary
LuxuryMode
LuxuryMode

Reputation: 33741

Bit mask in swapping bits algorithm

Having a bit of trouble fully understanding a basic algo which takes a number x and swaps the bits at positions i and j. The algo is this well-known one

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

As I understand it, the algo works by

  1. checking if the bits at position i and j are different. If not, we're done bc swapping the same bits is the same as doing nothing
  2. if they are different then we swap them by flipping the bits. We can do this with XOR.

What I don't fully understand is how the constructing of the bit mask works. I get that the goal of the mask is to identify the subset of bits we want to toggle, but why is (1 << i) | (x << j) the way to do that? I think I see it for a second, then I lose it.

EDIT:

Think I see it now. We're simply creating two binary numbers, one with a bit set in the i position and one with a bit set in the j position. By ORing these, we have a number with bits set in the i and j positions. We can apply this mask to our input x because x ^ 1 = 0 when x = 1 and 1 when x = 0 to swap the bits.

Upvotes: 0

Views: 507

Answers (1)

Gene
Gene

Reputation: 46960

Your initial intuition that something looks fishy is correct. There's a typo:

> def swap_bits(x, i, j):
...     if (x >> i) & 1 != (x >> j) & 1:
...         bit_mask = (1 << i) | (x << j)
...         x ^= bit_mask
...     return x
... 
>>> swap_bits(0x55555, 1, 2)
1048579
>>> hex(swap_bits(0x55555, 1, 2))
'0x100003'
>>>

The answer should have been 0x55553. A corrected version would have

  bit_mask = (1 << i) | (1 << j)

I agree with one of the comments that this method begs for an if-less implementation. In C:

unsigned swap_bits(unsigned val, int i, int j) {
  unsigned b = ((val >> i) ^ (val >> j)) & 1;
  return ((b << i) | (b << j)) ^ val;
}

Upvotes: 1

Related Questions