Most efficient way to find 1s in a binary word?

I am unsure what something like this would be called, (hence the clumsy title) but I need something like this for something I'm working on. I can't describe it well in words, but I hope this drawing explains for me:

What would be the fastest 开发者_开发问答way of getting the number of "on-bits", "3" in this example, when everything after the arbitrary "index" (5 for example) is to be ignored?

In addition to what has already been said, I would like to bring it to your attention that many compilers offer a build-in popcnt that may be faster than doing it manually (then again, maybe not, be sure to test it). They have the advantage of probably compiling to a single popcnt opcode if it's available in your target architecture (but I heard they do stupid slow things when falling back to a library function), whereas you'd be very lucky if the compiler detected one of the algorithms from Sean's bithacks collection (but it may).

For msvc, it's __popcnt (and variants), for gcc it's __builtin_popcount (and variants), for OpenCL (ok you didn't ask for that, but why not throw it in) it's popcnt but you must enable cl_amd_popcnt.

First do input &= 0xfffffff8 (or the equivalent for your input type) to clear the three rightmost bits. Then take your pick from here.

Something like the following:

int
countOnes( unsigned value, int top )
{
    assert( top >= 0 && opt < CHAR_BIT * sizeof( unsigned ) );
    value &= ~(~0 << top);
    int results = 0;
    while ( value != 0 ) {
        ++ results;
        value &= value - 1;
    }
    return results;
}

This depends on the somewhat obscure fact that i & (i - 1) resets the low order bit.

A lookup table will give you this information in constant time.