CODEWITHSUNDEEP
pythonintegerbit-manipulation
David Chouinard
David Chouinard

Reputation: 6836

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.

Upvotes: 51

Views: 97749

Answers (15)

kimstik
kimstik

Reputation: 1889

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

Upvotes: 2

nneonneo
nneonneo

Reputation: 179392

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.

Upvotes: 0

Wolfram
Wolfram

Reputation: 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!

Upvotes: 1

Gradon Li
Gradon Li

Reputation: 1

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)

Upvotes: 0

lkcl
lkcl

Reputation: 197

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.

Upvotes: -1

Bruce
Bruce

Reputation: 189

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

Upvotes: 18

theb33k
theb33k

Reputation: 41

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]

Upvotes: 4

personal_cloud
personal_cloud

Reputation: 4484

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

Upvotes: 3

Sof
Sof

Reputation: 21

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

Upvotes: 2

Sudip Ghimire
Sudip Ghimire

Reputation: 111

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

Upvotes: 11

Fred Foo
Fred Foo

Reputation: 363487

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

Upvotes: 3

bluefoggy
bluefoggy

Reputation: 1041

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

Upvotes: 0

Jay Wang
Jay Wang

Reputation: 2840

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.

Upvotes: 8

Paul Hankin
Paul Hankin

Reputation: 58201

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

Upvotes: 3

nneonneo
nneonneo

Reputation: 179392

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.

Upvotes: 72

Related Questions