Counting bits in large string / bit vector

[Peter Otten]

bmacinnis at comcast.net wrote:

> In Perl I can create a large bit vector as follows:

> vec($bitmap,10000000,1) = 0;    # this will create a bit string of all
> zeros

> To set bits I may using commands like:

>      vec($bitmap,1000, 1) = 1          # turn on bit 1000
>      vec($bitmap,10000, 1) = 1        # turn on bit 10000
>      vec($bitmap,1000000, 1) = 1     # turn on bit 10000000

> which would set three bits in the string $bitmap - Note: in perl I don't
> even have to declare $bitmap until I use it in the vec command.
> Anyway there is a very cool perl command which return the number of bits
> set in a large bitmap string instantly.
 
> The command is:

>      $setbits = unpack("%32b*", $bitmap);

> Which in this case would store the number 3 in $setbits

> Is there an equivalent command in python that would immediately provide
> the number of set bits in a large bit vector/string
> I know I could loop through but when you have 10,000,000 or 100,000,000
> bits, the looping takes quite a while the perl unpack is instant.

With numpy:

>>> b = numpy.zeros(10**7, dtype=bool)
>>> for x in 3, 4, 6: b[10**x] = True
...
>>> b.sum()
3

I don't know how it's implemented, but it seems to be quite fast.