Friday, August 6, 2010

Bit Flipping in Python

In Python you can access bits directly with the &, |, ^, ~, <<, >> operators on integer objects.

An example bit transformation might be one that moves all of the set bits in a 12 bit number to the left and all of the unset bits in the same 12 bit number to the right.

For example the 12 bit number 101101000001 would be transformed into the 12 bit number 111110000000 using that transformation.

This example bit manipulation can be concisely written in Python as:

n1 = int("101101000001", 2)
bc = sum(1 for i in range(12) if n1 & (1 << i))
n2 = int(("1" * bc) + ("0" * (12 - bc)))

In Python 2.6 and later this example can more concisely be written as:

n1 = 0b101101000001
bc = sum(1 for i in range(12) if n1 & (1 << i))
n2 = sum(1 << i for i in range(11, (11 - bc), -1))

The generic 12 bit manipulation can be more re-usably written as:

# The 12 bits
b12 = tuple(1 << i for i in range(11, -1, -1))

# There are only 13 solutions
result_numbers = tuple(sum(b12[i] for i in range(c)) for c in range(13))
result_strings = tuple(("1" * i) + ("0" * (12 - i)) for i in range(13))

original_number = int("101101000001", 2)
bit_count = sum(1 for i in range(12) if original_number & b12[i])
transformed_number = result_numbers[bit_count]
print result_strings[bit_count]

The Python 2.6 and later version is:

# The 12 bits
b12 = tuple(1 << i for i in range(11, -1, -1))

# There are only 13 solutions
result_numbers = tuple(sum(b12[i] for i in range(c)) for c in range(13))
result_strings = tuple(bin(i) for i in result_numbers)

original_number = 0b101101000001
bit_count = sum(1 for i in range(12) if original_number & b12[i])
# Updated 2011-01-08
# in python 2.7 and later the above can be further optimized
# using range(original_number.bit_length) in place of range(12)
transformed_number = result_numbers[bit_count]
print result_strings[bit_count]

There is no need to define a function call or set of function calls. Bit manipulation easily lends itself to mapping list indexes to result sets that can be prebuilt to aid in readability and execution speed.

1 comment:

Muchlis said...

Nokia N900 tempted on Android Gingerbread