Geek Answers Handbook

Smooth way to reverse (binary) digits of a number in Python?

I am looking for a slick function that changes the digits of a binary representation of a number.

If f were such a function, I would have

int(reversed(s),2) == f(int(s,2)) whenever s is a string of zeros and ones starting with 1.

Now I am using lambda x: int(''.join(reversed(bin(x)[2:])),2)

as for brevity, but it seems like a pretty cool way to do it.

I was wondering if there was a nicer (possibly faster) way with bitwise operators and what not.

+6
source share
6 answers

What about

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

or

 int(bin(n)[:1:-1], 2)

The second method seems to be the faster of the two, however both methods are much faster than your current method:

 import timeit print timeit.timeit("int('{0:b}'.format(n)[::-1], 2)", 'n = 123456') print timeit.timeit("int(bin(n)[:1:-1], 2)", 'n = 123456') print timeit.timeit("int(''.join(reversed(bin(n)[2:])),2)", 'n = 123456') 
  1.13251614571
 0.710681915283
 2.23476600647
+6
source

You can do this using shift operators, for example:

 def revbits(x): rev = 0 while x: rev <<= 1 rev += x & 1 x >>= 1 return rev

This doesn't seem to be faster than your method, though (actually, a bit slower for me).

+7
source

Here is my suggestion:

 In [83]: int(''.join(bin(x)[:1:-1]), 2) Out[83]: 9987

The same method, slightly simplified.

+2
source

I would say that your current method works fine, but you can lose the list() call, since str.join() will take any iterations:

 def binary_reverse(num): return int(''.join(reversed(bin(num)[2:])), 2)

It is also not recommended to use lambda for anything other than the simplest of functions, where it will be used only once and will make the surrounding code more clear, being built-in.

The reason I feel this is normal as it describes what you want to do is take the binary representation of the number, cancel it, and then get the number again. This makes this code very readable, and this should be a priority.

+2
source

There is an entire half of the Hacker Delight chapter devoted to this problem (Section 7-1: Reversible Bits and Bytes) using binary operations, bit offsets, and other goodies. It all seems to be possible in Python , and it should be much faster than binary-string and inverse methods.

The book is not publicly available, but I found this blog post that discusses some of them. The method shown in the blog post follows the following quote from the book:

Bit reversal can be performed quite efficiently by replacing adjacent single bits, then replacing adjacent 2-bit fields, etc., as shown below. These five assignment statements can be executed in any order.

http://blog.sacaluta.com/2011/02/hackers-delight-reversing-bits.html

+1
source 
 >>> def bit_rev(n): ... return int(bin(n)[:1:-1], 2) ... >>> bit_rev(2) 1 >>>bit_rev(10) 5
+1
source

More articles:


All Articles