Flipping bits in python

Question

Hello,

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).

Answer 2

I don't know python so I am just thinking this from a pure mathsy agorithmy point of view...

It occurs to me that for the first part a more efficient method might be to construct a mask of the bits you want to switch first as an integer. To make life easy for me I'm going to assume that you are counting your lower and upper bounds from the least significant bit being 0 and the most significant being 31 (or whatever is appropriate for the length of an int in your case).

If you want bits n to m (m>n) to be flipped then the binary representation of the number 2^(m+1)-2^n will have these bits set. Then do an XOR and you do all the swaps in one go. The computer should be abel to do these in one go probably rather than one per bit swap.

As for the counting I'm not sure. There are ways to count the number of set bits in a number. I'm not sure if you get a gain in efficiency to use the above bitmask with an AND to 0 out all the bits you don't care about counting nad then use those algorithms or if you are best off modifying them to work for you. I dont' know how they work off the top of my head though. :)

Answer 3

def bitflip(n,range):
    bitfliplen = range[1]-range[0]
    return n ^ ((2**bitfliplen-1) << (range[0]))

Running:

>>> a = 47727124L
>>> b = bitflip(a,(5,10))
>>> print "a: {0:b}\nb: {1:b}".format(a,b)
a: 10110110000100001000010100
b: 10110110000100000111110100
>>>

Answer 4

For bit counting, once you've masked out the range you are interested in, see the bitCount() routine on the python BitManipulation wiki page which implements Brian Kernighan's scheme:

def bitCount(int_type):
    count = 0
    while(int_type):
        int_type &= int_type - 1
        count += 1
    return(count)