In EDA, and many other fields, one of the recurring problem is counting the number of set bits in an integer or bitset. For example, in Urbana, our randomized SAT solver, we routinely have to check how many unsatisfied clauses we have to check how far we are from the solution.

To check the number of bit set in a bitset or an integer, (for simplicity I assume we are dealing with 64-bit integers, or unsigned long long int in C++), I normally use:

  • The Good: This algorithm is very fast, specially if there are a few set bits in the integer. The while loop continues to count until the last bit set to 1 and then terminates.
  • The Bad: subtractions are a bit expensive,
  • The Ugly: when there are too many 1s, we have to count all the bits, which is as expensive as a naive approach.

The better, more versatile, but not necessary faster approach to count the number of set bits is to use C++ bitsets. Bitsets can be constructed from/converted to 64-bit integers. They also provide a series of helper methods, including count() which counts the number of set bits, any(), all() and none().

Internally, bitset counts are usually implemented using a lookup table. Here is how Visual Studio implements the count() method:

The _Bitsperhex array contains the number of set bits in hexadecimal digits, indexed by the digit, for example 5’s binary representation, 0101 contains 2, so _Bitsperhex[5]=2, _Bitsperhex[0xA]=2, etc. This function picks one digit at a time from the bitset by anding the _wordval & 0xF, looks up the number of set bits from the lookup table and adds that number to _val, then shifts for 4 bits (_wordval >>= 4).

The fastest approach to count the number of the bits is to use SSE4’s _popcnt64 instruction. The catch is the older/mobile processors might not have the popcnt instruction, so we have to check the __cpuid before hand to ensure this instruction exists.