How std::popcount Counts Set Bits in C++

This article explores std::popcount, introduced in C++20, and examines how it achieves maximum performance when counting set bits (1s) in an integer. You will learn about the role of the <bit> header, how modern compilers map this standard function directly to CPU-level assembly instructions, how hardware architectures like x86 and ARM process these operations, and how compilers handle fallback scenarios on older hardware.

The Purpose of std::popcount

Introduced in the C++20 standard within the <bit> header, std::popcount computes the population count—the number of bits set to 1—in an unsigned integer. Prior to C++20, developers had to rely on non-standard compiler intrinsics such as GCC's and Clang's __builtin_popcount or MSVC's __popcnt, or write custom bit-manipulation loops.

std::popcount standardizes this functionality across all conforming compilers. It is declared as a constexpr function and requires an unsigned integer type (unsigned int, unsigned long, uint64_t, etc.), returning an int containing the total count of set bits.

Direct Mapping to Hardware Instructions

The primary advantage of std::popcount over a manual loop is that modern processors include dedicated silicon for counting set bits in a single execution cycle or very low latency. Modern optimizing compilers recognize std::popcount as an intrinsic and substitute the function call with native CPU instructions.

x86-64 Architecture

On x86-64 platforms supporting the POPCNT instruction set (introduced with Intel's Nehalem microarchitecture and AMD's SSE4a/Barcelona), the compiler replaces std::popcount with the single machine instruction:

popcnt eax, edi

For 64-bit integers (uint64_t), the 64-bit variant is emitted:

popcnt rax, rdi

The POPCNT instruction calculates the result using dedicated hardware adders inside the CPU execution units, usually finishing within one to three clock cycles with high throughput, completely avoiding any branching.

ARM and AArch64

On 64-bit ARM architectures (AArch64), bit counting is handled through SIMD or dedicated integer bit manipulation:

  • In environments using the ARM Neon engine, the compiler typically moves the scalar integer to a vector register and executes VCNT (Vector Count), followed by an addition or reduction step.
  • With modern ARM extensions supporting scalar bit manipulation, instructions such as CNT directly handle the operation.

Compilation Flags and Instruction Availability

Because POPCNT was not part of the original x86-64 baseline specification, compilers do not emit the popcnt instruction by default unless instructed to target a CPU architecture that supports it.

If compiling with GCC or Clang using generic settings (e.g., -O2), the compiler cannot assume the target machine supports the instruction. In this scenario, it will emit a fallback algorithm or a call to a runtime library helper. To enable direct assembly emission, target-specific flags are required:

  • -march=native: Tells the compiler to use all instruction sets available on the host machine.
  • -mpopcnt: Explicitly enables the POPCNT instruction.
  • -msse4.2: Enables SSE 4.2 instructions, which include POPCNT.

On MSVC, the /O2 flag combined with architectures that naturally support the instruction will enable hardware instruction emission.

Software Fallback (SWAR)

When hardware support is unavailable or disabled via compiler flags, std::popcount does not revert to an iterative loop like Brian Kernighan’s algorithm (n &= (n - 1)), which has variable runtime and branch penalties.

Instead, compilers generate branch-free, parallel bit-twiddling algorithms known as SIMD Within A Register (SWAR). A standard 64-bit SWAR implementation masks and adds adjacent bits in parallel:

x = x - ((x >> 1) & 0x5555555555555555);
x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
x = (x + (x >> 4)) & 0x0F0F0F0F0F0F0F0F;
return (x * 0x0101010101010101) >> 56;

This sequence takes a constant number of arithmetic operations (shifts, masks, additions, and a multiplication) and executes without conditional branches. While slightly slower than a dedicated POPCNT instruction, it is significantly faster than any loop-based approach.

Summary of Performance Advantages

  1. Elimination of Branches: Eliminates branch misprediction penalties entirely, maintaining consistent pipeline flow.
  2. Single-Instruction Execution: Lowers the operation to one instruction (POPCNT, VCNT) when enabled by compiler target flags.
  3. Compile-Time Evaluation: Because it is marked constexpr, bit counts of compile-time constants are evaluated entirely during compilation, resulting in zero runtime overhead.