What is the fastest way to count set bits in UInt32

Question

What is the fastest way to count the number of set bits (i.e. count the number of 1s) in an UInt32 without the use of a look up table? Is there a way to count in O(1)?

Answer 1

The bit-twiddling hacks page has a number of options.

Of course, you could argue that iterating over all 32 possible bits is O(N) in that it's the same cost every time :)

For simplicity, I'd consider the lookup-table-per-byte approach, or Brian Kernighan's neat idea which iterates as many times as there are bits set, which I'd write as:

public static int CountBits(uint value)
{
    int count = 0;
    while (value != 0)
    {
        count++;
        value &= value - 1;
    }
    return count;
}

If you don't like the idea of populating a 256-entry lookup table, a lookup-per-nybble would still be pretty fast. Mind you, it's possible that 8 array lookups might be slower than 32 simple bit operations.

Of course, it's worth testing your app's real performance before going to particularly esoteric approaches... is this really a bottleneck for you?

Answer 2

Is a duplicate of: how-to-implement-bitcount-using-only-bitwise-operators or best-algorithm-to-count-the-number-of-set-bits-in-a-32-bit-integer

And there are many solutions for that problem. The one I use is:

    int NumberOfSetBits(int i)
    {
        i = i - ((i >> 1) & 0x55555555);
        i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
        return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
    }

Answer 3

In .NET Core 3.0 the x86 popcnt intrinsic has been exposed, allowing you to perform a single-instruction population count calculation on a uint or uint64.

int setBits = System.Runtime.Intrinsics.X86.Popcnt.PopCount(value);

There is also a 64-bit version System.Runtime.Intrinsics.X86.Popcnt.X64.PopCount() that can be used on a ulong when running on a 64-bit CPU.