Reversing bits of Python integer

Question

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.

Finisterre

For step one, you can use str(bin(65))[2:].zfill(8). To lazy/tired to look further into this now. But you should probably just do as larsmans says. – Annelleannemarie

"The issue with step #1 is retrieving the full decimal representation with filling zeros (ie. 65 = 01000001, not 1000001)." Why should it be 01000001 and not 1000001? Why shouldn't it be 00000000000000000000000001000001 (32 bits) instead? Or any other arbitrary number of bits? – Venesection

Answer 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.

Balbo

Elegant and concise. I needed to change the format string to '{:08b}' to work as specified. – Nerveracking

Ah, yes, he wanted the filling zeroes. I'll amend. – Balbo

If I do int('{:b}'.format(65)[::-1], 2), I just get 65 as output. Using {:08b} instead of {:b} gives the correct result though, so +1 for elegant solution. – Annelleannemarie

Yes, sorry. Slight reading comprehension fail, answer amended. – Balbo

@Balbo & Shane, thanks to both of you. I read up on format() and this makes a lot sense. Definitely the most elegant solution. – Finisterre

Didn't understand [::-1] portion, Can someone explain please ? – Inhabit

This is list slicing which causes iterating the list in the reverse order. – Milore

Answer 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

Crossbreed

FYI: the link is now broken. Is this function limited to ints or will it work on numbers of type bignum? – Taurus

Since the link is broken, the same procedure can be found here with a bit more information: https://mcmap.net/q/150811/-in-c-c-what-39-s-the-simplest-way-to-reverse-the-order-of-bits-in-a-byte – Mint

Answer 3

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))

Franza

Answer 4

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.

Patman

You have to take into account the number of bits to be reversed. For example, you want to reverse bits in a byte. You expect that 0x1 will be translated to 0x80 (0b00000001 -> 0b10000000). And with current implementation, you'll still get 0x1 on the output – Vanhouten

Answer 5

You could also use a Look up table (that can be generated once using methods above):

LUT = [0, 128, 64, 192, 32, 160, 96, 224, 16, 144, 80, 208, 48, 176, 112, 240,
       8, 136, 72, 200, 40, 168, 104, 232, 24, 152, 88, 216, 56, 184, 120,
       248, 4, 132, 68, 196, 36, 164, 100, 228, 20, 148, 84, 212, 52, 180,
       116, 244, 12, 140, 76, 204, 44, 172, 108, 236, 28, 156, 92, 220, 60,
       188, 124, 252, 2, 130, 66, 194, 34, 162, 98, 226, 18, 146, 82, 210, 50,
       178, 114, 242, 10, 138, 74, 202, 42, 170, 106, 234, 26, 154, 90, 218,
       58, 186, 122, 250, 6, 134, 70, 198, 38, 166, 102, 230, 22, 150, 86, 214,
       54, 182, 118, 246, 14, 142, 78, 206, 46, 174, 110, 238, 30, 158, 94,
       222, 62, 190, 126, 254, 1, 129, 65, 193, 33, 161, 97, 225, 17, 145, 81,
       209, 49, 177, 113, 241, 9, 137, 73, 201, 41, 169, 105, 233, 25, 153, 89,
       217, 57, 185, 121, 249, 5, 133, 69, 197, 37, 165, 101, 229, 21, 149, 85,
       213, 53, 181, 117, 245, 13, 141, 77, 205, 45, 173, 109, 237, 29, 157,
       93, 221, 61, 189, 125, 253, 3, 131, 67, 195, 35, 163, 99, 227, 19, 147,
       83, 211, 51, 179, 115, 243, 11, 139, 75, 203, 43, 171, 107, 235, 27,
       155, 91, 219, 59, 187, 123, 251, 7, 135, 71, 199, 39, 167, 103, 231, 23,
       151, 87, 215, 55, 183, 119, 247, 15, 143, 79, 207, 47, 175, 111, 239,
       31, 159, 95, 223, 63, 191, 127, 255]

def reverseBitOrder(uint8):
    return LUT[uint8]

Unheardof

Answer 6

There's no need, and no way, to "convert a decimal integer to binary representation". All Python integers are represented as binary; they're just converted to decimal when you print them for convenience.

If you want to follow this solution to the reversal problem, you only need to find appropriate numbits. You can either specify this by hand, or compute the number of bits needed to represent an integer n with n.bit_length() (new in Python 2.7 and 3.1).

However, for 65, that would give you 7, as there's no reason why 65 should require any more bits. (You might want to round up to the nearest multiple of 8...)

Fillister

Not really right, as you can get a string representing the bits (bin(n), or '{:b}'.format(n)). Plus, you can use .bit_length() to find the exact number of bits needed to represent a number. – Balbo

@nneonneo: I was assuming the OP wants to work on the integer itself rather than a string representation, given the links. But thanks for the bit_length method, didn't know about that. – Fillister

Answer 7

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))

Sharpnosed

Answer 8

An inefficient but concise method that works in both Python 2.7 and Python 3:

def bit_reverse(i, n):
    return int(format(i, '0%db' % n)[::-1], 2)

For your example:

>>> bit_reverse(65, 8)
130

Alvin

Answer 9

Regularly there is the need to apply this operation on array of numbers and not for single number. To increase speed, it's probably better to use NumPy array. There are two solutions.

x1.34 faster than second solution:

import numpy as np
def reverse_bits_faster(x):
  x = np.array(x)
  bits_num = x.dtype.itemsize * 8
  # because bitwise operations may change number of bits in numbers
  one_array = np.array([1], x.dtype)
  # switch bits in-place
  for i in range(int(bits_num / 2)):
    right_bit_mask = (one_array << i)[0]
    left_bit = (x & right_bit_mask) << (bits_num - 1 - i * 2)
    left_bit_mask = (one_array << (bits_num - 1 - i))[0]
    right_bit = (x & left_bit_mask) >> (bits_num - 1 - i * 2)
    moved_bits_mask = left_bit_mask | right_bit_mask
    x = x & (~moved_bits_mask) | left_bit | right_bit
  return x

Slower, but more easy to understand (based on solution proposed by Sudip Ghimire):

import numpy as np
def reverse_bits(x):
  x = np.array(x)
  bits_num = x.dtype.itemsize * 8
  x_reversed = np.zeros_like(x)
  for i in range(bits_num):
    x_reversed = (x_reversed << 1) | x & 1
    x >>= 1
  return x_reversed

Rodolphe

Answer 10

All what you need is numpy

import numpy as np
x = np.uint8(65)
print( np.packbits(np.unpackbits(x, bitorder='little')) )

performance:

py -3 -m timeit "import numpy as np; import timeit; x=np.uint8(65); timeit.timeit(lambda: np.packbits(np.unpackbits(x, bitorder='little')), number=100000)"
1 loop, best of 5: 326 msec per loop

Margeret

Answer 11

I found this one the fastest on my ESP32 with micropython:

@measure
def rev03(n):
    b = ((n * 0x0802 & 0x22110) | (n * 0x8020 & 0x88440)) * 0x10101 >> 16
    return b & 255

Second if you insist to use string is this one:

@measure
def rev01(n):
    b = bin(n)
    rev = b[-1:1:-1]
    rev = rev + (8 - len(rev))*'0'
    return int(rev, 2)

I used my following decorator:

def measure(f):
    def wrapper(*args, **kwargs):
        start = time.time_ns()
        for i in range(100000):
            n = f(*args, **kwargs)
        end = time.time_ns()
        print("time(ns) = {}\n", end - start)
        return n

    return wrapper

Have fun to evaluate!

Chiliasm

Answer 12

One more way to do it is to loop through the bits from both end and swap each other. This i learned from EPI python book.

i = 0; j = 7
num = 230
print(bin(num))
while i<j:
    # Get the bits from both end iteratively
    if (x>>i)&1 != (x>>j)&1:
        # if the bits don't match swap them by creating a bit mask
        # and XOR it with the number 
        mask = (1<<i) | (1<<j)
        num ^= mask
    i += 1; j -= 1
print(bin(num))

Harness

Answer 13

The first and second steps have a very neat algorthom:

num = int(input())

while num > 0:
  reminder = num % 2
  print(f'{str(reminder)}', end = '')
  num = int(num / 2)

Passable

Answer 14

You do not need to get the binary as a string. Instead, you can directly reverse bits by the XOR operator ^. If you'd like to work with a fixed number of bits, then you can use:

def reverse_int_bits(x: int, n_bits: int):
    return x ^ ((1 << n_bits) - 1)

Otherwise, you can first find the next power 2 number and then similarly use it to mask and reverse the bits:

def reverse_int_bits(x: int):
    return x ^ (next_pow2(x) - 1)

def next_pow2(x: int):
    return 1 << (x - 1).bit_length()

Wrapper

Answer 15

bin(x)[:1:-1]

one line, and it automatically goes for the top bit. (edit: use zfill or rjust to get a fixed width - see below)

>>> x = 0b1011000
>>> bin(x)[:1:-1]
'0001101'
>>> x = 0b100
>>> bin(x)[:1:-1]
'001'

the "0b" on the front of the text-conversion is stripped by the "1" in [:1:-1] which, after the inversion (by -1) has 1 automatically added to it (sigh, range is really weird) before being used as the start point not the end.

you'll need zero-padding on the front to get it a fixed-width reversing but even there [:1:-1] will still do the auto-length-detection

zfill does the job but you need to split off the "0b" from bin() first, then zfill, then invert (then convert to int)

length=10
bin(x)[2:].zfill(length)[::-1]
int(bin(x)[2:].zfill(length)[::-1],2)

using ljust:

bin(x)[:1:-1].ljust(length, '0')

strangely although longer i find ljust clearer.

Ultimatum