bit count or bit set && Python3

Discussion in 'Python' started by Charles Hixson, Oct 25, 2012.

  1. 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?

    --
    Charles Hixson
    Charles Hixson, Oct 25, 2012
    #1
    1. Advertising

  2. Charles Hixson

    rusi Guest

    On Oct 25, 7:56 pm, 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?
    >
    > --
    > Charles Hixson


    You may have already checked it out and find it unsuitable...
    I guess you know that python has good implementation of sets
    http://docs.python.org/library/sets.html ?
    rusi, Oct 25, 2012
    #2
    1. Advertising

  3. Charles Hixson

    Terry Reedy Guest

    On 10/25/2012 12:13 PM, rusi wrote:
    > On Oct 25, 7:56 pm, 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?


    If I wanted 1000s of fast limited-length bitsets, I would consider using
    Cython to make an extension class.

    --
    Terry Jan Reedy
    Terry Reedy, Oct 25, 2012
    #3
  4. Charles Hixson

    Guest

    On Thursday, October 25, 2012 7:56:25 AM UTC-7, Charles Hixson wrote:
    > In Python3 is there any good way to count the number of on bits in an
    > integer (after an & operation)?


    You may want to look at gmpy2[1] and the popcount() function.

    >
    > 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,
    >


    Whether or not gmpy2 is considered light-weight is debateable. :)

    > 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?
    >


    [1] http://code.google.com/p/gmpy/

    >
    >
    > --
    >
    > Charles Hixson
    , Oct 26, 2012
    #4
  5. Charles Hixson

    Guest

    On Thursday, October 25, 2012 7:56:25 AM UTC-7, Charles Hixson wrote:
    > In Python3 is there any good way to count the number of on bits in an
    > integer (after an & operation)?


    You may want to look at gmpy2[1] and the popcount() function.

    >
    > 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,
    >


    Whether or not gmpy2 is considered light-weight is debateable. :)

    > 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?
    >


    [1] http://code.google.com/p/gmpy/

    >
    >
    > --
    >
    > Charles Hixson
    , Oct 26, 2012
    #5
  6. wrote:
    > On Thursday, October 25, 2012 7:56:25 AM UTC-7, Charles Hixson wrote:
    >> In Python3 is there any good way to count the number of on bits in an
    >> integer (after an& operation)?

    > You may want to look at gmpy2[1] and the popcount() function.
    >
    >> 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,
    >>

    > Whether or not gmpy2 is considered light-weight is debateable. :)
    >
    >> 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?
    >>

    > [1] http://code.google.com/p/gmpy/
    >
    >>
    >> --
    >>
    >> Charles Hixson

    I can see many times when that would be useful, but for this particular
    case I think that bin(val).count("1") is probably the better solution.
    The other options that I need are already available directly in integer
    numbers, and I will be surprised if I need more than a 32-bit set, so
    integers should be a reasonable approach. It doesn't seem to have the
    overhead that I feared a string conversion would have (possibly because
    converting an integer to a bit string is trivial), so I don't think
    that gmpy would add value to this program.

    Next I need to decide about weak pointers, and then shelve vs.
    tokyocabinet. (I sort of don't like shelve, because of its use of
    pickle, with the attendent security risks. OTOH, the file will be local
    to the computer, not going over the net, which minimizes that. Still, I
    may decide to reimplement it using ast.literal_eval, as I'm not
    intending to store anything that it won't handle.
    Charles Hixson, Oct 26, 2012
    #6
    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. MRAB
    Replies:
    0
    Views:
    144
  2. Steven D'Aprano

    Re: bit count or bit set && Python3

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

    Re: bit count or bit set && Python3

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

    bit count or bit set && Python3

    Charles Hixson, Oct 25, 2012, in forum: Python
    Replies:
    0
    Views:
    97
    Charles Hixson
    Oct 25, 2012
  5. Charles Hixson

    bit count or bit set && Python3

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

Share This Page