Bit-twiddling in Python 2.6

Bit manipulation, or bit-twiddling, has always been possible in Python. The only problem was that there was no built-in support for displaying numbers in binary format. Python 2.6 fixes this.

There's a new generation of programmers who didn't spend their childhoods designing spaceship graphics on graph-paper and manually converting them from binary (the graph-paper image) to integers, byte-by-byte for their ZX Spectrum 48K. They don't yet know the wonders on bit-twiddling; are you among them?

Why? Bit-twiddling is efficient and concise. If you ever find yourself iterating over the bits in an integer to achieve some end, it's a near certainty that bit-twiddling can achieve that end, in just a few processor cycles rather than thousands.

Any array of booleans can be converted into a set of bits and thence twiddled.

Jargon First of all, you'll need to know that negative integers on almost all systems are represented in two's complement format.

Bit-twiddlers refer to a 1 as a 'set' bit and a 0 as 'clear' bit. 'Set' and 'clear' are verbs meaning to set a bit to one or zero, respectively. A new byte (or word, or long, etc.) is presumed to be 'clear' - i.e. all bits set to zero, an integer value of zero. 'Higher' bits are to the left and 'lower' bits are to the right.

You'll also need to be familiar with the bitwise operators: & (and), | (or), ^ (xor), and ~ (not). They are demonstrated in a section further below.

Examples



python's binary support

x = 0b00101010
42
bin(42) # note: this omits leading zeros
'0b101010'

problems with Python's bin...

bin(-42)         # 'bin' shows a sign, rather than printing an explicit two's complement format
'-0b101010'
bin(28 - 42)   # this prints two's complement representation of 42 for a byte
'0b11010110'
bin(232 - 42)  # this prints two's complement representation of 42 for a 32-bit long word
'0b11111111111111111111111111010110'

Make wrapper for 'bin' which shows Y bit's two's complement, instead of negatives. def tcbin(x, y=8):



"""
This function returns the padded, two's complement representation of x, in y-bits.
It is conventional for y to be 8, 16, 32 or 64, though y can have any non-zero positive value. 
"""
if x >= (2**(y - 1)) or x < -(2**(y - 1) or y < 1):
    raise Exception("Argument outside of range.")
if x >= 0:
    binstr = bin(x)
    # pad with leading zeros
    while len(binstr) < y + 2:
        binstr = "0b0" + binstr[2:]
    return binstr
return bin((2**y) + x) # x is negative

Basic operators.



x = 0b00101010
y = 0b00001111

tcbin(x & y) # set all bits which are set in x and y
'0b00001010'

tcbin(x | y) # set all bits which are set in x or y
'0b00101111'

tcbin(x ^ y) # set all bits which are set in x or y, but not both (x xor y)
'0b00100101'

tcbin(~x) # set all bits which are clear in x
'0b11010101'

Two's complement identity.



x = 0b00101010
tcbin(-x)
'0b11010110'
tcbin(~x)
'0b11010101'
tcbin(~x + 1)
'0b11010110'

Extract lowest set bit.



x = 0b00101010
tcbin(x & -x)
'0b00000010'

Mask for bits above and including lowest bit set



x = 0b00101010
tcbin(x | -x)
'0b11111110'

Mask for bits above lowest set bit.



x = 0b00101010
tcbin(x ^ -x)
'0b11111100

Clear lowest set bit.



x = 0b00101010
tcbin(x & (x - 1))
'0b00101000'

Set all bits below lowest set bit.



x = 0b00101010
tcbin(x | (x - 1))
'0b00101011'

Shift bits rights so that lowest set bit is at the right.



x = 0b00101010
tcbin (x / (x & -x))
'0b00010101'

More useful ideas (if you can read C) can be found at Sean Eron Anderson's page.

Posted on 05 October 2008.