Bit enumeration algorithms

Discussion in 'C++' started by, Aug 3, 2006.

  1. Guest

    I have an algorithm question for you all:

    I am familiar with table-free bit counting algorithms such as the MIT
    HAKMEM algorithm and others. However, I have an application where I
    need to enumerate the indexes of every bit in an integer (64 bit
    integer in this case). For example, if I had the following 8-bit


    I want an array to contain the numbers [ 3,6 ] along with an integer
    '2' telling me that two bits were set.... or I want the same
    information in some other form.

    So right now what I'm doing is looping, testing, and shifting. It's
    not bad, but I'm wondering if there's anything faster.

    I tried inline assembly language using the 'bsf' instruction (bit scan
    forward), but found that using this instruction seems to be *slower*
    (yeah, I was surprised too!) than just the naive loop-test-shift even
    though far fewer instructions were executed in the 'bsf'
    implementation. I think this instruction uses a lot of clock cycles.
    I know it's a rarely used instruction, so it's possible that modern
    processors choose to implement it inefficiently to make room for more
    efficient implementations of commonly used instructions. (This was an
    Athlon-MP machine.)

    So right now loop-test-shift with no special inline assembly language
    voodoo is the fastest thing I've come up with. I do of course test for
    the integer being zero as it loops, so it will abort the loop if no
    more bits are left.

    By the way, what I end up doing at the end of this is to pick a set bit
    at random. If there's any fast shortcut to doing this and skipping the
    whole bit enumeration, that would work too. Note that in my
    application the bits are usually going to be sparse, so just testing
    random bits turns out to be no better than enumerating bits and then
    picking one.

    So any wizards want to take this one up?

    , Aug 3, 2006
    1. Advertisements

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. Replies:
    Timothy Bendfelt
    Jan 19, 2007
  2. Replies:
    Robert Mabee
    Aug 3, 2006
  3. Replies:
    Juha Nieminen
    Aug 22, 2007
  4. puvit82
    Feb 1, 2008
  5. Jeff.M
    Lasse Reichstein Nielsen
    May 4, 2009

Share This Page