efficient(-ish) bit reversal of small-ish integers

import struct

BYTE_REV = "".join([chr(int("{0:08b}".format(n)[::-1], 2)) for n in range(256)])
QUAD = struct.Struct('>Q')
QUAD_R = struct.Struct('<Q')

def int_reverse(n, base=64):
    if n >= 2**64:
        raise ValueError("n must be less than 2**64; recieved "+str(n))
    return QUAD_R.unpack(QUAD.pack(n).translate(BYTE_REV))[0] >> (64-base)


>>> int_reverse(1, 3)
4L
>>> int_reverse(1, 4)
8L
>>> int_reverse(1, 5)
16L
>>> int_reverse(5, 3)
5L
>>> int_reverse(3, 3)
6L

This is useful for example for doing a binary search of a space.


>>> [int_reverse(n, 10) for n in range(2**10)][:16]
[0, 512L, 256L, 768L, 128L, 640L, 384L, 896L, 64L, 576L, 320L, 832L, 192L, 704L, 448L, 960L]

First it does 0, then 1/2 way through the range, then 1/4, then 3/4, etc...  Sometimes this is a useful search order.