# C++ Bit Manipulation Counting bits set

## Example

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 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);
`````` PDF - Download C++ for free