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