Counting bits in large string / bit vector

Ian Kelly ian.g.kelly at gmail.com
Mon Sep 26 12:39:16 EDT 2011


On Sep 26, 2011 1:49 AM, <bmacinnis at comcast.net> wrote:
> Is there an equivalent command in python that would immediately provide
the number of set bits in a large bit vector/string

Besides what others have said, if you expect the number of bits set to be
small, you might just use a set.

bits = set()
# set bit 1000
bits.add(1000)
# clear bit 2000000
bits.discard(2000000)
# test bit 1000
if 1000 in bits:
    pass
# get number of bits set
len(bits)

All of these operations are O(1), but if you expect to set a very large
number of bits, then the space trade-off may not be practical.

Cheers,
Ian
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20110926/12411128/attachment.html>


More information about the Python-list mailing list