How to improve Python code for swapping bits of a 32-bit integer

Question

Swap bits - Coding interview question

A few days ago, I came across the following coding interview question (using Python).

Problem:

Given a 32-bit integer, swap the 1st and 2nd bit, 3rd and 4th bit, up til the 31st and 32nd bit.

Here's some starting code and an example:

def swap_bits(num):
    # Fill this in.

print(f"0b{swap_bits(0b10101010101010101010101010101010):032b}")
# 0b01010101010101010101010101010101

My Solution:

def swap_bits(num):
    num_out = 0
    for ii in range(16):
        num_out += (num & (2**(2*ii))) << 1
        num_out += (num & (2**(2*ii+1))) >> 1
    return num_out

print(f"0b{swap_bits(0b10101010101010101010101010101010):032b}")

# Output: 
# 0b01010101010101010101010101010101

My Question to You:

Do you have any suggestions for improvement, in terms of efficiency, length of code, readability, or whatever. I will highly appreciate your feedback. Thanks!

Regarding readability I suggest using comments and so-called function's docstrings, be aware that you should keep balance between being too wordy (like commenting every line) and too comment-shy (like not comments at all) — Daweo
– Daweo, Commented May 14, 2020 at 10:53

score 8 · Accepted Answer · 2020-05-14 11:02:39Z

8

You don't need a loop for this (well, you must not use a loop for this, in a coding interview), just a couple of binary operators:

>>> n = 752846942
>>> bin(n)
'0b101100110111111000100001011110'
>>> bin(((n >> 1) & 0x55555555) | ((n & 0x55555555) << 1))
'0b011100111011110100010010101101'

I added a leading 0 to the last number, to make the result more easily comparable to n.

What's the trick?

Consider your number as a vector of bits. Exchanging pairs of bits is equivalent to moving all even-numbered bits one position to the left, and all odd-numbered bits one position to the right (assuming bit numbering start at 0, begining with the LSB on the right).

Moving to the left and to the right is just a binary shift: n << 1 and n >> 1. But if I simply do (n << 1) | (n >> 1), I will move all bits, and the result will be wrong. So, first select which bits you want: the even bits are 0x55555555 & n, the odd bits are n & 0xaaaaaaaa.

So a possibility is:

((n & 0x55555555) << 1) | ((n & 0xaaaaaaaa) >> 1)

Another way is to select bits after the shift but before the binary or:

((n << 1) & 0xaaaaaaaa) | ((n >> 1) & 0x55555555)

Since the bit parity is reversed by the shift, I just have to swap the constants 0x55555555 and 0xaaaaaaaa.

To get the same constant on both side of the binary or, I select before the shift on one side, and after on the other.

edited May 14, 2020 at 11:02

answered May 14, 2020 at 10:40

user13517564

Sign up to request clarification or add additional context in comments.

5 Comments

Thierry Lathuille Over a year ago

How did you get the magical n, if not with int('0b1010101010101010101010101010101', 2)? Explaining that would add some value to your answer...

user13517564 Over a year ago

@ThierryLathuille Shorter than 0b010.... Actually I computed it with eval("0b" + "01" * 16). Just too lazy to type it.

Thierry Lathuille Over a year ago

Actually, I copied it from your answer, that was even easier ;) But you could probably add it as well to your answer!

user13517564 Over a year ago

@ThierryLathuille You remark made me think again: I replaced it with the hex value.

Zabir Al Nazi Nabil Over a year ago

That is pretty optimized, but kindly drop an explanation when you write such a compressed expression out of your pocket.

Zabir Al Nazi Nabil · Accepted Answer · 2020-05-14 10:52:33Z

0

You can definitely get rid of the exponentiation which is costly. It's possible to compress it more but as long as every operator is binary the complexity stays the same.

# to keep the code readable
def swapBits(n, p1, p2): 

    ''' Move p1'th to rightmost side '''
    bit1 = (n >> p1) & 1

    ''' Move p2'th to rightmost side '''
    bit2 = (n >> p2) & 1

    ''' XOR the two bits '''
    x = (bit1 ^ bit2) 

    ''' Put the xor bit back to their  
        original positions '''
    x = (x << p1) | (x << p2) 

    ''' XOR 'x' with the original number  
        so that thetwo sets are swapped '''
    result = n ^ x 
    return result 

n = 11
print(bin(n))
k = 0
for i in range(32):
    n = swapBits(n, k, k+1)
    k+= 2

print(n)
print(bin(n))

edited May 14, 2020 at 10:52

answered May 14, 2020 at 10:50

Zabir Al Nazi Nabil

11.3k4 gold badges38 silver badges71 bronze badges

4 Comments

user13517564 Over a year ago

Don't use a loop. Really. It's a one liner with binary ops.

Zabir Al Nazi Nabil Over a year ago

Yes, but how do you come up with such a compressed expression in 3 minutes window, I'm really curious. Can you add some explanation with your code too?

user13517564 Over a year ago

Actually it was in less than 3 minutes. You have to know your binary ops well. There are lots of tricks with them, see for instance the book Hacker's Delight, or this. For this case, I remembered the trick to reverse bits (here)

Zabir Al Nazi Nabil Over a year ago

Thanks for the link, it's indeed helpful + your explanation now makes your expression pretty obvious. I also noticed you're big on Mathematics site so now it makes me less guilty for not thinking it before :)

Collectives™ on Stack Overflow

How to improve Python code for swapping bits of a 32-bit integer

Swap bits - Coding interview question

Problem:

My Solution:

My Question to You:

2 Answers 2

5 Comments

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

Swap bits - Coding interview question

Problem:

My Solution:

My Question to You:

2 Answers 2

5 Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related