Re: bit count or bit set && Python3

Discussion in 'Python' started by Antoon Pardon, Oct 26, 2012.

1. Antoon PardonGuest

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
while full < bits:
for i in range(index):
full = (full << shift) + full
index = index + 1
shift = 2 * shift
shift = 1
for i in range(index):
bits = ((bits >> shift) & mask) + (bits & mask)
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

Antoon Pardon, Oct 26, 2012