Re: bit count or bit set && Python3

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

  1. 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 = (mask << shift) + mask
    mask.append(full)
    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
    #1
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Charles Hixson

    bit count or bit set && Python3

    Charles Hixson, Oct 25, 2012, in forum: Python
    Replies:
    5
    Views:
    238
    Charles Hixson
    Oct 26, 2012
  2. MRAB
    Replies:
    0
    Views:
    164
  3. Steven D'Aprano

    Re: bit count or bit set && Python3

    Steven D'Aprano, Oct 25, 2012, in forum: Python
    Replies:
    12
    Views:
    285
    Neil Cerutti
    Oct 26, 2012
  4. Mark Lawrence

    Re: bit count or bit set && Python3

    Mark Lawrence, Oct 25, 2012, in forum: Python
    Replies:
    0
    Views:
    159
    Mark Lawrence
    Oct 25, 2012
  5. Charles Hixson

    bit count or bit set && Python3

    Charles Hixson, Oct 25, 2012, in forum: Python
    Replies:
    0
    Views:
    113
    Charles Hixson
    Oct 25, 2012
Loading...

Share This Page