Countones
Countones, also known as population count or Hamming weight, is a measure used in computer science to count the number of set bits (1s) in a binary word or bitstring. It is a common primitive in algorithms that manipulate bit vectors, as well as in cryptography, data compression, error detection, and similarity measures. The function can operate on unsigned integers of fixed width or on arbitrary-length bitstrings.
Common methods to compute countones include:
- Naive: test each bit individually and increment a counter for every 1, yielding time proportional to
- Kernighan’s method: repeatedly clear the lowest set bit with n = n & (n - 1) and increment a
- Lookup tables: precompute counts for small chunks (such as 8 or 16 bits) and sum across the
- SWAR (SIMD Within A Register) / parallel counting: use bitwise shifts and masks to count bits in
- Hardware support: many modern CPUs provide a dedicated popcnt instruction that counts bits in a register
Edge cases and considerations:
- The result depends on the bit width and representation; for signed integers, the interpretation may differ
- For arbitrary-length bitstrings, the count is the sum across all words or blocks.
- The term popcount or bit_count is commonly used in programming languages; many libraries provide built-in functions