# 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);