Reversing bits of Python integer

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

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

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.

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]

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

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

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

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

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; x=np.uint8(65); np.packbits(np.unpackbits(x, bitorder='little'))"
100000 loops, best of 5: 3.51 usec per loop

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!

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

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)

If you find yourself needing to bit-reverse a lot of integers, or reversing large integers, this is the fastest way:

# Calculate this translation table only once and cache it for future conversions
transtable = bytes([int(f"{i:08b}"[::-1], 2) for i in range(256)])
def rev_fast(n, w):
    rem = w % 8
    if rem:
        # peel off the low bits and flip them separately
        low = n & ((1 << rem) - 1)
        hi = n >> rem
        hirev = int.from_bytes(hi.to_bytes(w // 8, "little").translate(transtable), "big")
        shift = w - rem - (8 - rem)
        if shift < 0:
            return hirev | (transtable[low] >> -shift)
        else:
            return hirev | (transtable[low] << shift)
    else:
        return int.from_bytes(n.to_bytes(w // 8, "little").translate(transtable), "big")

This is between 3x and 10x faster than the top answer, and many orders of magnitude faster than any of the bit-by-bit approaches.

Benchmark:

32-bit integers

nneonneo's first answer: 200000 loops, best of 5: 1.54 usec per loop
Sudip's bit-by-bit answer: 50000 loops, best of 5: 7.85 usec per loop
Bruce's bit-twiddling answer (only for 32-bit): 200000 loops, best of 5: 1.34 usec per loop
this answer: 500000 loops, best of 5: 529 nsec per loop

This is 3x faster than the top answer.

2048-bit integers

nneonneo's first answer: 20000 loops, best of 5: 11.9 usec per loop
Sudip's bit-by-bit answer: 500 loops, best of 5: 771 usec per loop
this answer: 200000 loops, best of 5: 1.6 usec per loop

This is 7x faster than the top answer, and much faster than the bit-by-bit algorithm.

Why is this fast? At its core, this is using the endianness arguments of int.from_bytes/int.to_bytes to achieve the flipping, combined with a quick way to flip the bits in each byte (bytes.translate). All the heavy operations are done in C, making this fast. The bit-by-bit solutions are slow in Python as they entail creating new Python big integers on every iteration (as integers are immutable) - this makes them take quadratic time.

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.