Home Original page

Bitsets in Python

Anton Vredegoor anton at vredegoor.doge.nl
Thu Feb 5 17:23:35 EST 2004 
Jeff Epler <jepler at unpythonic.net> wrote:

>I also don't think there's anything in the standard library for it.
>I vaguely recall talk that putting this in the 'array' module might be
>the right thing to do:
>    >>> array.array(array.BIT, '\xaa')
>    array(array.BIT, [1, 0, 1, 0, 1, 0, 1, 0])

Alternatively there could be support for "generating all tuples" a la
Knuth. The code below could be used for conversions to and from
binary, but it would be also be useful for datetime computations,
lexical permutations and other things. Doing it this way would solve
various requests simultaneously.

For datetime one could use [24,60,60] as bases, for binary with 3 bits
one could use [2,2,2], for permutations of a list of length 5 one
could use [5,4,3,2] as bases (although after using this as a starting
point I found some shorter lexical ranking and unranking functions).

Anton

def rank(L,bases):
    res,multiplier = 0,1
    for x,b in zip(L[::-1],bases[::-1]):
        res += x*multiplier
        multiplier *= b
    return res

def unrank(d,bases):
    res = []
    for b in bases[::-1]:
        d,m = divmod(d,b)
        res.append(m)
    return res[::-1]

def test():
    bases = [2,2,2]
    n = reduce(lambda x,y: x*y,bases)
    for i in range(n):
        x = unrank(i,bases)
        print i,x
        assert i == rank(x,bases)

if __name__=='__main__':
    test()

output:

0 [0, 0, 0]
1 [0, 0, 1]
2 [0, 1, 0]
3 [0, 1, 1]
4 [1, 0, 0]
5 [1, 0, 1]
6 [1, 1, 0]
7 [1, 1, 1]
More information about the Python-list mailing list