How do you reverse the significant bits of an integer in python?

Question

What is the best way to reverse the significant bits of an integer in python and then get the resulting integer out of it?

For example I have the numbers 1,2,5,15 and I want to reverse the bits like so:

original      reversed
1  - 0001  -  1000 - 8
2  - 0010  -  0100 - 4
5  - 0101  -  1010 - 10
15 - 1111  -  1111 - 15

Given that these numbers are 32 bit integers how should I do this in python? The part I am unsure about is how to move individual bits around in python and if there is anything funny about using a 32bit field as an integer after doing so.

PS This isn't homework, I am just trying to program the solution to a logic puzzle.

Answer 1

This is a fast way to do it:

I got it from here

BitReverseTable256 = [0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0, 0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0,
                      0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8, 0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8,
                      0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4, 0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x74, 0xF4,
                      0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC, 0x1C, 0x9C, 0x5C, 0xDC, 0x3C, 0xBC, 0x7C, 0xFC,
                      0x02, 0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2, 0x12, 0x92, 0x52, 0xD2, 0x32, 0xB2, 0x72, 0xF2,
                      0x0A, 0x8A, 0x4A, 0xCA, 0x2A, 0xAA, 0x6A, 0xEA, 0x1A, 0x9A, 0x5A, 0xDA, 0x3A, 0xBA, 0x7A, 0xFA,
                      0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6, 0x16, 0x96, 0x56, 0xD6, 0x36, 0xB6, 0x76, 0xF6,
                      0x0E, 0x8E, 0x4E, 0xCE, 0x2E, 0xAE, 0x6E, 0xEE, 0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE,
                      0x01, 0x81, 0x41, 0xC1, 0x21, 0xA1, 0x61, 0xE1, 0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, 0xF1,
                      0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9, 0x69, 0xE9, 0x19, 0x99, 0x59, 0xD9, 0x39, 0xB9, 0x79, 0xF9,
                      0x05, 0x85, 0x45, 0xC5, 0x25, 0xA5, 0x65, 0xE5, 0x15, 0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5,
                      0x0D, 0x8D, 0x4D, 0xCD, 0x2D, 0xAD, 0x6D, 0xED, 0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD,
                      0x03, 0x83, 0x43, 0xC3, 0x23, 0xA3, 0x63, 0xE3, 0x13, 0x93, 0x53, 0xD3, 0x33, 0xB3, 0x73, 0xF3,
                      0x0B, 0x8B, 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB, 0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB,
                      0x07, 0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7, 0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7,
                      0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF, 0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF]
v = 32 # any int number will be reverse 32-bit value, 8 bits at time

c = BitReverseTable256[v & 0xff] << 24 |
    BitReverseTable256[(v >> 8) & 0xff] << 16 | 
    BitReverseTable256[(v >> 16) & 0xff] << 8 |
    BitReverseTable256[(v >> 24) & 0xff]

Answer 2

reversed_ = sum(1<<(numbits-1-i) for i in range(numbits) if original>>i&1)

Answer 3

If you truly want 32 bits rather than 4, then here is a function to do what you want:

def revbits(x):
    return int(bin(x)[2:].zfill(32)[::-1], 2)

Basically I'm converting to binary, stripping off the '0b' in front, filling with zeros up to 32 chars, reversing, and converting back to an integer.

It might be faster to do the actual bit work as in gnibbler's answer.

Answer 4

Numpy indexing arrays provide concise notation for application of bit reversal permutations.

import numpy as np

def bitrev_map(nbits):
  """create bit reversal mapping

  >>> bitrev_map(3)
  array([0, 4, 2, 6, 1, 5, 3, 7], dtype=uint16)
  >>> import numpy as np
  >>> np.arange(8)[bitrev_map(3)]
  array([0, 4, 2, 6, 1, 5, 3, 7])
  >>> (np.arange(8)[bitrev_map(3)])[bitrev_map(3)]
  array([0, 1, 2, 3, 4, 5, 6, 7])
  """
  assert isinstance(nbits, int) and nbits > 0, 'bit size must be positive integer'
  dtype = np.uint32 if nbits > 16 else np.uint16
  brmap = np.empty(2**nbits, dtype=dtype)
  int_, ifmt, fmtstr = int, int.__format__, ("0%db" % nbits)
  for i in range(2**nbits):
    brmap[i] = int_(ifmt(i, fmtstr)[::-1], base=2)
  return brmap

When bit reversing many vectors one wants to store the mapping anyway.

The implementation reverses binary literal representations.

Answer 5

This is the first link I found googling for "python bitwise" and it has a pretty good summary of how to do bit-twiddling in Python.

If you don't care too much about speed, the most straightforward solution is to go through each bit-place of the original number and, if it is set, set the corresponding bit of your return value.

def reversed( x, num_bits ):
    answer = 0
    for i in range( num_bits ):                   # for each bit number
        if (x & (1 << i)):                        # if it matches that bit
            answer |= (1 << (num_bits - 1 - i))   # set the "opposite" bit in answer
    return answer

I'm sure you could do this with a comprehension, too. If you really needed speed, you'd probably do it 8 bits at a time with a 256-value precomputed lookup table.

Answer 6

You can do something like this where you can define how many bits in the argument l.

def reverse(x, l):
    r = x & 1
    for i in range (1, l):
        r = r << 1 | (x >> i) & 1
    print(bin(r))
    return r