Reversing bits of Python integer

Given a decimal integer (eg. 65), how does one reverse the underlying bits in Python? i.e.. the following operation:

65 → 01000001 → 10000010 → 130

It seems that this task can be broken down into three steps:

1. Convert the decimal integer to binary representation
2. Reverse the bits
3. Convert back to decimal

Steps #2 and 3 seem pretty straightforward (see this and this SO question related to step #2), but I'm stuck on step #1. The issue with step #1 is retrieving the full decimal representation with filling zeros (ie. 65 = 01000001, not 1000001).

I've searched around, but I can't seem to find anything.

Solution 1:

int('{:08b}'.format(n)[::-1], 2)

You can specify any filling length in place of the 8. If you want to get really fancy,

b = '{:0{width}b}'.format(n, width=width)
int(b[::-1], 2)

lets you specify the width programmatically.

Solution 2:

If you are after more speed, you can use the technique described in http://leetcode.com/2011/08/reverse-bits.html

def reverse_mask(x):
    x = ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1)
    x = ((x & 0x33333333) << 2) | ((x & 0xCCCCCCCC) >> 2)
    x = ((x & 0x0F0F0F0F) << 4) | ((x & 0xF0F0F0F0) >> 4)
    x = ((x & 0x00FF00FF) << 8) | ((x & 0xFF00FF00) >> 8)
    x = ((x & 0x0000FFFF) << 16) | ((x & 0xFFFF0000) >> 16)
    return x

Solution 3:

def reverse_bit(num):
    result = 0
    while num:
        result = (result << 1) + (num & 1)
        num >>= 1
    return result

We don't really need to convert the integer into binary, since integers are actually binary in Python.

The reversing idea is like doing the in-space reversing of integers.

def reverse_int(x):
    result = 0
    pos_x = abs(x)
    while pos_x:
        result = result * 10 + pos_x % 10
        pos_x /= 10
    return result if x >= 0 else (-1) * result

For each loop, the original number is dropping the right-most bit(in binary). We get that right-most bit and multiply 2 (<<1) in the next loop when the new bit is added.

Solution 4:

best way to do is perform bit by bit shifting

def reverse_Bits(n, no_of_bits):
    result = 0
    for i in range(no_of_bits):
        result <<= 1
        result |= n & 1
        n >>= 1
    return result
# for example we reverse 12 i.e 1100 which is 4 bits long
print(reverse_Bits(12,4))

Solution 5:

You can test the i'th bit of a number by using a shift and mask. For example, bit 6 of 65 is (65 >> 6) & 1. You can set a bit in a similar way by shifting 1 left the right number of times. These insights gives you code like this (which reverses x in a field of 'n' bits).

def reverse(x, n):
    result = 0
    for i in xrange(n):
        if (x >> i) & 1: result |= 1 << (n - 1 - i)
    return result

print bin(reverse(65, 8))