On 25-10-12 16:47, Charles Hixson wrote:
> 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?
>
Some time ago I implemented this. Maybe you can use it as inspiration.
def CardSet(iter):
bits = 0L
for el in iter:
bits = bits | (1L << el)
return CardSetType(bits)
def CSt(*args):
return CardSet(args)
class CardSetType:
def __init__(self, bits):
self.bits = bits
def __str__(self):
return '{' + ','.join(map(str , self)) + '}'
def __repr__(self):
return 'CSt(' + ','.join(map(str , self)) + ')'
def __eq__(self, term):
return self.bits == term.bits
def __contains__(self, el):
return (1L << el) & self.bits == 1L << el
def __and__(self, term):
return CardSetType(self.bits & term.bits)
def __or__(self, term):
return CardSetType(self.bits | term.bits)
def __xor__(self, term):
return CardSetType(self.bits ^ term.bits)
def __sub__(self, term):
return CardSetType(self.bits & ~term.bits)
def __le__(self, term):
return self.bits & term.bits == self.bits
def __ge__(self, term):
return self.bits | term.bits == self.bits
def __len__(self):
bits = self.bits
full = 1L
shift = 1L
index = 0
mask = []
while full < bits:
for i in range(index):
mask[i] = (mask[i] << shift) + mask[i]
mask.append(full)
full = (full << shift) + full
index = index + 1
shift = 2 * shift
shift = 1
for i in range(index):
bits = ((bits >> shift) & mask[i]) + (bits & mask[i])
shift = 2 * shift
return int(bits)
def incl(self, el):
self.bits = self.bits | 1L << el
def excl(self, el):
self.bits = self.bits & ~(1L << el)
def __iter__(self):
return SetIterator(self.bits)
class SetIterator:
def __init__(self, bits):
self.bits = bits
self.offset = 0
def __iter__(self):
return self
def next(self):
if self.bits == 0:
raise StopIteration
else:
while True:
shift = 0
delta = 1
full = 1L
while (self.bits & full) == 0:
full = (full << delta) + full
shift = delta
delta = delta * 2
if shift == 0:
break
self.offset = self.offset + shift
self.bits = self.bits >> shift
result = self.offset
self.offset = self.offset + 1
self.bits = self.bits >> 1
return result
--
http://mail.python.org/mailman/listinfo/python-list
