Bit arrays.
Tim Peters
tim_one at email.msn.com
Sun Feb 13 08:44:52 CET 2000
[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
More information about the Python-list
mailing list