Flipping bits in python

Question

Given an integer n , i want to toggle all bits in the binary representation of that number in the range say lower to upper. To do this i do the following [bit_string is a string containing 1's and 0's and is a binary representation of n]

for i in range(lower,upper+1):
   n ^= (1 << len(bit_string)-1-i) #Toggle the ith bit

Then , i also need to determine that given a range, say lower to upper,how many bits are set.My code to do that is as follows :

number_of_ones = 0
for i in range(lower,upper+1):
    if(n & (1 << len(bit_string)-1-i)): #Check the ith bit
      number_of_ones+=1

But, if n is very large, i think these algorithms would be slow. Is there a way to make these two operations faster/more efficient ?

Thank You

Answer 1

For the "flipping", you can make a single bitmap (with ones in all positions of interest) and a single exclusive-or:

n ^= ((1<<upper)-1)&~((1<<lower)-1)

For bit-counts, once you isolate (n & mask) for the same "mask" as the above RHS, slicing it into e.g. 8-bit slices and looking up the 8-bit counts in a lookup table (just a simple list or array.array to prepare beforehand) is about the fastest approach.

gmpy has some useful and speedy bit-manipulation and counting operations, esp. faster than Python's native offerings if you're dealing with very long bit strings (more than a machine word's worth, so in Python they'd be long instances).