Bit arrays.

[Tim Peters]

[posted & mailed]

[rdudfield at my-deja.com]
> Just wondering if there is an efficient way in python to represent
> arrays or lists of bits?

Not particularly.

> The way that I am thinking of doing it is to make a class in python
> and do the following:
>
> Have set and get methods for arbitary places in the array.
>
> It would store the data in an array of ints (not sure what size yet).

By "array" you may mean either a Python list or an array from the std module
"array".  Both can be resized dynamically without trouble.  lists are
faster; arrays take less storage.

> ...
> The set method would be implemented in the following way:
>
> *Find which element in the array of ints that the bit is in.
> *Convert that int into a tupple/list/array of 1s and 0s.
> *Find which place in the new list of 1s, and 0s the bit which needs
> changing.
> *Change that bit.
> *Convert the list back into a number.

You can assume that a Python int contains at least 32 bits.  So given a
giant "bit index" i, the bit can be viewed as being bit number

    i & 0x1f   # last five bits

of int number

    i >> 5

Python's divmod can do both operations at once, so ...

    # set bit at bit index i
    intindex, bitnum = divmod(i, 32)
    # assuming self.data is either list or array
    self.data[intindex] = self.data[intindex] | (1 << bitnum)

That is, it's really the same way you'd implement a bit vector in C or C++.

> ...
> It would probably be worth doing this as a module in c/c++ no?

Depends entirely on how much speed you need.  Definitely worth prototyping
in Python first, though!  If it turns out that you *really* need, e.g., many
logical operations on bit vectors, you can easily switch to Python long
(unbounded) ints, where setting a bit is just

    data = data | (1L << i)

This takes time proportional to max(i, num_bits_in_data), though, while the
array/list-based approach takes time independent of those.

there's-more-than-one-slow-way-to-do-it-ly y'rs  - tim