populationcount

Population count, also called popcount, populationcount, or Hamming weight, is the operation that counts the number of set bits in the binary representation of a nonnegative integer. The result is the number of ones in the word. It is a fundamental primitive in low‑level programming and is used in algorithms that manipulate bitsets, measure similarity (Hamming distance), and perform fast set operations.

Software methods include straightforward loops that shift and test, Brian Kernighan’s method which repeatedly clears the least-significant set bit, and parallel or SWAR techniques that count bits in chunks using masks. Lookup-table approaches provide constant-time results with a precomputed table at the cost of memory.

Modern processors often provide a dedicated population count instruction, making the operation effectively constant time. Intel and AMD include POPCNT in modern x86‑64, ARM offers CNT/CNTL instructions, and many GPUs have similar facilities. High-level languages expose this via builtins or library calls, such as C/C++ __builtin_popcount, Java Long.bitCount, or Python int.bit_count.

Typical considerations include word size (32 vs 64 bits), unsigned interpretation, and portability across platforms. The exact API varies, but the concept remains the same: returning the number of 1s in a binary word to enable fast bitset operations, distance calculations, or population counts in probabilistic data structures.