Bitsets in Python

[Rajarshi Guha]

Hi,
does Python have any native support for bitsets? I dont seem to see
anything in the standard library?

Thanks,
Rajarshi

[Josiah Carlson]

Re: Bitsets in Python

> does Python have any native support for bitsets? I dont seem to see[color=blue]
> anything in the standard library?[/color]

What do you mean 'bitsets'? Give a list of functionality of your
'bitsets', and it will be easy for us to tell you whether Python
includes it.

- Josiah

[Matt]

Re: Bitsets in Python

Josiah Carlson <jcarlson@nospa m.uci.edu> wrote:[color=blue][color=green]
> > does Python have any native support for bitsets? I dont seem to see
> > anything in the standard library?[/color]
>
> What do you mean 'bitsets'? Give a list of functionality of your
> 'bitsets', and it will be easy for us to tell you whether Python
> includes it.[/color]

BitSets crop up in (at least) C++ and Java. They allow you operate on
a sequence of bits using a friendlier interface than hacking about
with ^,|,& et al on integers. The Java BitSet interface:

http://java.sun.com/j2se/1.4.1/docs/api/java/util/BitSet.html

I can't find anything like it in the standard library (If I've
overlooked it, I'd be chuffed to find out I'm wrong!). The OP might
find the following Cookbook recipe useful, though:

http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/219300

(At least I think so, I can't access the site at the moment...)

Matt

[Jeff Epler]

Re: Bitsets in Python

On Thu, Feb 05, 2004 at 05:50:57AM -0800, Matt wrote:[color=blue]
> I can't find anything like it in the standard library (If I've
> overlooked it, I'd be chuffed to find out I'm wrong!).[/color]

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:[color=blue][color=green][color=darkred]
>>> array.array(arr ay.BIT, '\xaa')[/color][/color][/color]
array(array.BIT , [1, 0, 1, 0, 1, 0, 1, 0])

numarray also has arrays of bool, though I have to confess I'm not sure
how they're stored:[color=blue][color=green][color=darkred]
>>> numarray.zeros( (16,), numarray.Bool)[/color][/color][/color]
array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], type=Bool)

Jeff

[Josiah Carlson]

Re: Bitsets in Python

[color=blue]
> BitSets crop up in (at least) C++ and Java. They allow you operate on
> a sequence of bits using a friendlier interface than hacking about
> with ^,|,& et al on integers. The Java BitSet interface:[/color]

I would suggest subclassing int:

class bitset(int):
def __getitem__(sel f, k):
return (2**k & self) >> k
def __setitem__(sel f, k, v):
#this doesn't work
if v:
return bitset(2**k | self)
elif self[k]:
return bitset(2**k ^ self)

Unfortunately, due to the semantics of item setting a[i] = j, you cannot
return anything from a setitem, and integers are immutable, so you
cannot modify bitset directly.

Sounds like something in need of a custom class. Thankfully it wouldn't
be too difficult.

- Josiah

[Graham Fawcett]

Re: Bitsets in Python

matt_crypto@yah oo.co.uk (Matt) wrote in message news:<94b59a36. 0402050550.442a 93d1@posting.go ogle.com>...[color=blue]
> Josiah Carlson <jcarlson@nospa m.uci.edu> wrote:[color=green][color=darkred]
> > > does Python have any native support for bitsets? I dont seem to see
> > > anything in the standard library?[/color]
> >
> > What do you mean 'bitsets'? Give a list of functionality of your
> > 'bitsets', and it will be easy for us to tell you whether Python
> > includes it.[/color]
>
> BitSets crop up in (at least) C++ and Java. They allow you operate on
> a sequence of bits using a friendlier interface than hacking about
> with ^,|,& et al on integers. The Java BitSet interface:
>
> http://java.sun.com/j2se/1.4.1/docs/...il/BitSet.html
>
> I can't find anything like it in the standard library (If I've
> overlooked it, I'd be chuffed to find out I'm wrong!). The OP might
> find the following Cookbook recipe useful, though:[/color]

Depending on your needs, you might find Sam Rushing's npstruct module
to be of use.

npstruct: An extension module useful for parsing and unparsing binary
data structures. Somewhat like the standard struct module, but with a
few extra features (bitfields, user-function-fields, byte order
specification, etc...) and a different API more convenient for
streamed and context-sensitive formats like network protocol packets,
image and sound files, etc...

http://nightmare.com/software.html

-- Graham

[Anton Vredegoor]

Re: Bitsets in Python

Jeff Epler <jepler@unpytho nic.net> wrote:
[color=blue]
>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:[color=green][color=darkred]
> >>> array.array(arr ay.BIT, '\xaa')[/color][/color]
> array(array.BIT , [1, 0, 1, 0, 1, 0, 1, 0])[/color]

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__=='__ma in__':
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]

[Rajarshi Guha]

Re: Bitsets in Python

On Tue, 03 Feb 2004 19:56:36 -0800, Josiah Carlson wrote:
[color=blue][color=green]
>> does Python have any native support for bitsets? I dont seem to see
>> anything in the standard library?[/color]
>
> What do you mean 'bitsets'? Give a list of functionality of your
> 'bitsets', and it will be easy for us to tell you whether Python
> includes it.[/color]

Sorry for th late reply. Thanks to everybody who responded.

A little background to the problem - I'm evaluating molecular fingerprints
which use bitsets of length N and set certain bits on depending on whether
a feature is present. So I was essentially looking for Java style bitsets.

In the end I wrote a small class which did the job (since all I need is to
keep track of which positions are on)

Thanks,

--
-------------------------------------------------------------------
Rajarshi Guha <rajarshi@presi dency.com> <http://jijo.cjb.net>
GPG Fingerprint: 0CCA 8EE2 2EEB 25E2 AB04 06F7 1BB9 E634 9B87 56EE
-------------------------------------------------------------------
Q: What's purple and commutes?
A: An abelian grape.