The most efficient way to find 1s in a binary word?

Question

I'm not sure if something like this will be called (hence the clumsy headline), but I need something similar for something I'm working on. I cannot describe it well in words, but I hope this illustration explains to me:

What would be the fastest way to get the number of "on-bits", "3" in this example, when everything is needed after ignoring an arbitrary "index" (for example, 5)?

Answer 1

First do input &= 0xfffffff8 (or the equivalent for your input type) to clear the three input &= 0xfffffff8 bits. Then choose your choice .

Answer 2

In addition to what has already been said, I would like to draw your attention to the fact that many compilers offer built-in popcnt, which can be faster than doing it manually (again, maybe not, be sure to check it out). They have an advantage, perhaps compiling the popcnt operation into one code if it is available in your target architecture (but I heard that they do stupid slow things when they return to the library function), while you will be very lucky if the compiler detects one of the algorithms from the collection of Sean's chests (but it may be).

For msvc, it __ popcnt (and options), for gcc it __builtin_popcount (and options), for OpenCL (it’s good that you didn’t ask for this, but why not throw it away) it popcnt, but you have to include cl_amd_popcnt.

Answer 3

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) discards the least significant bit.

Answer 4

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