Finding out no bits set in a variable in faster manner

Question

Possible Duplicate:
Best algorithm to count the number of set bits in a 32-bit integer?

Finding out the no. bits sets in a variable is easier. But how could we perform the same operation in fastest method ?

Answer 1

This page on Bit Twiddling Hacks covers several techniques to count the number of bits set, and discusses the performance of each.

Answer 2

The bit twiddling hacks page has a variety of suggestions.

Answer 3

int i, size, set;
for (i = 1, size = sizeof(int) * 8; i <= size; i++)
{
    if (value & (0 << 2 * i)) set++;    
}

Answer 4

If variable is an integer, you can count bits using

   public static int BitCount(int x)
        { return ((x == 0) ? 0 : ((x < 0) ? 1 : 0) + BitCount(x <<= 1)); }

Explanation: Recursive, if number is zero, no bits are set, and function returns a zero else, it checks the sign bit and if set stores 1 else stores a 0, then shifts the entire number one bit to the left eliminating the sign bit just examined, and putting a zero in rightmost bit, and calls itself again with new left-Shifted value.

Overall result is to examine each bit from leftmost to rightmost, and for each one set, stores on stack whether that bit was set (as 1/0), left-Shits next bit into sign bit position and resurses. When it finally gets to the last bit set , the value will be zero and recursion will stop. Function then returns up the call stack, adding up all the temp values it stored on the way down. Returns total

Answer 5

If you're asking the question, then chances are __builtin_popcount on gcc is at least as fast as what you're currently doing. __builtin_popcount can generally be beaten on x86, so presumably on other CPUs too, but you don't say what your CPU is other than "embedded". It affects the answer.

If you're not using gcc, then you need to look up how to do a fast popcount on your actual compiler and/or CPU. For obvious reasons, there is no such thing as "the fastest way to count set bits in C".

Answer 6

Counting the set bits in a variable is termed the "population count", shortened to "popcount".

A very good micro-benchmark of different software algorithms is given at: http://www.dalkescientific.com/writings/diary/archive/2008/07/05/bitslice%5Fand%5Fpopcount.html

AMD "Barcelona" processors onwards have a fast fixed-cost instruction, which in GCC you can get using __builtin_popcount

On Intel boxes I've found that __builtin_ffs in a loop works best for sparse bit sets.

Its something you can't rely upon; you must micro-benchmark if this is important to you.

Answer 7

I highly recommend reading Hacker's Delight for all questions regarding various forms of bit-twiddling. For counting bits, in particular, it analyzes several algorithms depending on the instructions you might have available to you.