Python and Bitwise Rotation

The other day I found myself wondering how to perform bitwise rotations in Python, particular bit rotations (circular shifts). There’s lots of complex ways to do it –¬†bitstring, bitarray, and others – but I wanted a more compact and efficient method.

Turns out it’s relatively easy… the C idiom for bitwise rotation is a good starting point, but I’ve extended it to handle an arbitrary unsigned bit string (one that is first truncated to fit in the width of the virtual “register” we’re shifting in – just so it doesn’t go totally bonkers if it gets an “impossible” value). It’s also¬†robust enough to handle excessive rotations (where a value only n bits long is rotated more than n bits).

Here it is along with some test code:

###########################################################################
# Rotating bits (tested with Python 2.7)

from __future__ import print_function   # PEP 3105

# max bits > 0 == width of the value in bits (e.g., int_16 -> 16)

# Rotate left: 0b1001 --> 0b0011
rol = lambda val, r_bits, max_bits: \
    (val << r_bits%max_bits) & (2**max_bits-1) | \
    ((val & (2**max_bits-1)) >> (max_bits-(r_bits%max_bits)))

# Rotate right: 0b1001 --> 0b1100
ror = lambda val, r_bits, max_bits: \
    ((val & (2**max_bits-1)) >> r_bits%max_bits) | \
    (val << (max_bits-(r_bits%max_bits)) & (2**max_bits-1))

max_bits = 16  # For fun, try 2, 17 or other arbitrary (positive!) values

print()
for i in xrange(0, max_bits*2-1):
    value = 0xC000
    newval = rol(value, i, max_bits)
    print("0x%08x << 0x%02x --> 0x%08x" % (value, i, newval))

print()
for i in xrange(0, max_bits*2-1):
    value = 0x0003
    newval = ror(value, i, max_bits)
    print("0x%08x >> 0x%02x --> 0x%08x" % (value, i, newval))

###########################################################################

2 Comments

Leave a Reply

Your email address will not be published. Required fields are marked *

*