Bitwise Programming in Python

Question

I'm trying to write a program to solve an ACM problem, and it has to be very fast. A mathematically fast approach to the problem is to use bitwise computations. However, I'm using python and I'm having trouble performing these computations at bit level. The problems are:

1. Counting the number of 1's and 0's in the bit. For example, how do we calculate the the binary digit 100010 has two 1's and 4 0's. The only approach I can imagine is to convert it to a string and and count them. But this conversion cancels out all the speed gained by working at bit level in the first place.
2. How to represent a string input describing the binary digit such as '100101' as an actual binary digit in Python? Currently I have a function that converts the bit into an integer and I perform the bitwise operations on the ints.
3. Is there a bit data type? That is can I receive the input as a bit rather than a string or an int?

I did consider writing a class such as bitSet in C++, but I have a feeling this will not be very fast either. P.S. the binary digits I'm working with can be as large as 1000 bits and I might have to work with a 1000 such binary digits, so efficiency is imperative.

Answer 1

Here's a well-known algorithm for counting the one-bits:

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

The point is that x-1 has the same binary representation as x, except that the least least significant one-bit is cleared to 0 and all the trailing 0's are set to one. So, setting x = x & (x-1) simply clears the least significant one-bit.