# Counting bits set

suggest changeThe 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);`