bit count or bit set && Python3

[Charles Hixson]

In Python3 is there any good way to count the number of on bits in an
integer (after an & operation)?
Alternatively, is there any VERY light-weight implementation of a bit
set? I'd prefer to use integers, as I'm probably going to need
thousands of these, if the tests work out. But before I can test, I
need a decent bit counter. (shift, xor, &, and | are already present
for integer values, but I also need to count the number of "true" items
after the logical operation. So if a bitset is the correct approach,
I'll need it to implement those operations, or their equivalents in
terms of union and intersection.)

Or do I need to drop into C for this?

 

[rusi]

In Python3 is there any good way to count the number of on bits in an
integer (after an & operation)?
Alternatively, is there any VERY light-weight implementation of a bit
set?  I'd prefer to use integers, as I'm probably going to need
thousands of these, if the tests work out.  But before I can test, I
need a decent bit counter.  (shift, xor, &, and | are already present
for integer values, but I also need to count the number of "true" items
after the logical operation.  So if a bitset is the correct approach,
I'll need it to implement those operations, or their equivalents in
terms of union and intersection.)

Or do I need to drop into C for this?

You may have already checked it out and find it unsuitable...
I guess you know that python has good implementation of sets
http://docs.python.org/library/sets.html ?

 

[Terry Reedy]

If I wanted 1000s of fast limited-length bitsets, I would consider using
Cython to make an extension class.

 

[casevh]

In Python3 is there any good way to count the number of on bits in an
integer (after an & operation)?

You may want to look at gmpy2[1] and the popcount() function.

Alternatively, is there any VERY light-weight implementation of a bit
set? I'd prefer to use integers, as I'm probably going to need
thousands of these, if the tests work out. But before I can test, I
need a decent bit counter. (shift, xor, &, and | are already present
for integer values, but I also need to count the number of "true" items
after the logical operation. So if a bitset is the correct approach,

Whether or not gmpy2 is considered light-weight is debateable.

I'll need it to implement those operations, or their equivalents in
terms of union and intersection.)



Or do I need to drop into C for this?

[1] http://code.google.com/p/gmpy/

 

[casevh]

In Python3 is there any good way to count the number of on bits in an
integer (after an & operation)?

You may want to look at gmpy2[1] and the popcount() function.

Alternatively, is there any VERY light-weight implementation of a bit
set? I'd prefer to use integers, as I'm probably going to need
thousands of these, if the tests work out. But before I can test, I
need a decent bit counter. (shift, xor, &, and | are already present
for integer values, but I also need to count the number of "true" items
after the logical operation. So if a bitset is the correct approach,

Whether or not gmpy2 is considered light-weight is debateable.

I'll need it to implement those operations, or their equivalents in
terms of union and intersection.)



Or do I need to drop into C for this?

[1] http://code.google.com/p/gmpy/

 

[Charles Hixson]

In Python3 is there any good way to count the number of on bits in an
integer (after an& operation)?

You may want to look at gmpy2[1] and the popcount() function.

Alternatively, is there any VERY light-weight implementation of a bit
set? I'd prefer to use integers, as I'm probably going to need
thousands of these, if the tests work out. But before I can test, I
need a decent bit counter. (shift, xor,&, and | are already present
for integer values, but I also need to count the number of "true" items
after the logical operation. So if a bitset is the correct approach,

Whether or not gmpy2 is considered light-weight is debateable.

I'll need it to implement those operations, or their equivalents in
terms of union and intersection.)



Or do I need to drop into C for this?

[1] http://code.google.com/p/gmpy/

I can see many times when that would be useful, but for this particular
case I think that bin(val).count("1") is probably the better solution.
The other options that I need are already available directly in integer
numbers, and I will be surprised if I need more than a 32-bit set, so
integers should be a reasonable approach. It doesn't seem to have the
overhead that I feared a string conversion would have (possibly because
converting an integer to a bit string is trivial), so I don't think
that gmpy would add value to this program.

Next I need to decide about weak pointers, and then shelve vs.
tokyocabinet. (I sort of don't like shelve, because of its use of
pickle, with the attendent security risks. OTOH, the file will be local
to the computer, not going over the net, which minimizes that. Still, I
may decide to reimplement it using ast.literal_eval, as I'm not
intending to store anything that it won't handle.