Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #32201

Re: bit count or bit set && Python3

Show key headers only | View raw

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

Back to comp.lang.python | Previous | Next | Find similar | Unroll thread

Thread

Re: bit count or bit set && Python3 Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2012-10-26 10:31 +0200

csiph-web