Counting bits set

suggest change

The population count of a bitstring is often needed in cryptography and other applications and the problem has been widely studied.

The naive way requires one iteration per bit:

unsigned value = 1234;
unsigned bits = 0;  // accumulates the total number of bits set in `n`

for (bits = 0; value; value >>= 1) {
  bits += value & 1;
}

A nice trick (based on http://stackoverflow.com/documentation/c%2b%2b/3016/bit-manipulation/17299/remove-rightmost-set-bit ) is:

unsigned bits = 0;  // accumulates the total number of bits set in `n`

for (; value; ++bits) {
  value &= value - 1;
}

It goes through as many iterations as there are set bits, so it’s good when value is expected to have few nonzero bits.

The method was first proposed by Peter Wegner (in CACM 3 / 322 - 1960) and it’s well known since it appears in C Programming Language by Brian W. Kernighan and Dennis M. Ritchie.

This requires 12 arithmetic operations, one of which is a multication:

unsigned popcount(std::uint64_t x)
{
  const std::uint64_t m1  = 0x5555555555555555;  // binary: 0101...
  const std::uint64_t m2  = 0x3333333333333333;  // binary: 00110011..
  const std::uint64_t m4  = 0x0f0f0f0f0f0f0f0f;  // binary: 0000111100001111

  x -= (x >> 1) & m1;             // put count of each 2 bits into those 2 bits
  x = (x & m2) + ((x >> 2) & m2); // put count of each 4 bits into those 4 bits 
  x = (x + (x >> 4)) & m4;        // put count of each 8 bits into those 8 bits 
  return (x * h01) >> 56;  // left 8 bits of x + (x<<8) + (x<<16) + (x<<24) + ... 
}

This kind of implementation has the best worst-case behavior (see Hamming weight for further details).

Many CPUs have a specific instruction (like x86’s popcnt) and the compiler could offer a specific (non standard) built in function. E.g. with g++ there is:

int __builtin_popcount (unsigned x);

Found a mistake? Have a question or improvement idea? Let me know.

Table Of Contents