What is the fastest way to count bits in UInt32

Question

What is the fastest way to count the number of bits (i.e., count the number 1) in UInt32 without using a lookup table? Is there a way to count in O(1) ?

Answer 1

Is a duplicate: 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 to this problem. I use:

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

Answer 2

There are several options on the bit-twiddling hacks page.

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

For simplicity, I would consider the lookup-table-per-byte approach or Brian Kernigan’s clear idea, which repeats as many times as there is a bit that I would 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 lookup table with 256 entries, browsing for nybble will still be pretty fast. Keep in mind that it is possible that searching in 8 arrays may be slower than 32 simple bit operations.

Of course, it is worth checking the real performance of your application before moving on to especially esoteric approaches ... is this really a bottleneck for you?