bitcount

Bitcount, also known as population count or Hamming weight, is the number of 1 bits in the binary representation of an integer. It is a basic bitwise operation used in many algorithms, data structures, and hardware implementations.

A straightforward way to compute bitcount is to repeatedly test the least significant bit and shift the number, counting each 1 encountered. This naive approach has time proportional to the number of bits, typically O(b) for b-bit integers, and can be optimized in practice.

Faster methods include Kernighan’s algorithm, which iterates only over set bits: while n != 0, n = n & (n - 1); count++. The number of iterations equals the number of 1s in the value, often much smaller than b. Lookup table approaches precompute popcounts for small blocks (such as bytes) and combine results, trading memory for speed. Other techniques use SWAR (SIMD Within A Register) and related bit-twiddling sequences to reduce multiple bits with a small, fixed sequence of operations. Many modern CPUs provide a hardware-accelerated popcount instruction, enabling constant-time counting for typical word sizes.

Built-in support is common in programming languages. C/C++ exposes facilities such as __builtin_popcount and __builtin_popcountll; Java provides Integer.bitCount and Long.bitCount; several languages offer equivalent functions or methods that call the hardware instruction when available.

Applications of bitcount include bitboard games and graphics, data compression and cryptography, error detection and correction, bloom filters, cardinality estimation, and fast similarity measures in databases and search systems. It remains a staple primitive in performance-critical code.