Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder1.news.weretis.net!feeder.erje.net!newsfeed.xs4all.nl!newsfeed6.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Date: Fri, 26 Oct 2012 10:31:43 +0200
From: Antoon Pardon <antoon.pardon@rece.vub.ac.be>
User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.1.16) Gecko/20120925 Iceowl/1.0b1 Icedove/3.0.11
MIME-Version: 1.0
To: python-list@python.org
Subject: Re: bit count or bit set && Python3
References: <5089511E.4090009@earthlink.net>
In-Reply-To: <5089511E.4090009@earthlink.net>
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.2887.1351240305.27098.python-list@python.org>
Lines: 117
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:32201

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