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

Question

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?

Answer 1

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.

Answer 2

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