The Hamming weight of a string is the number of symbols that are different from the zero-symbol of the alphabet used. It is thus equivalent to the Hamming distance from the all-zero string of the same length. For the most typical case, a given set of bits, this is the number of bits set to 1, or the digit sum of the binary representation of a given number and the ℓ₁ norm of a bit vector. In this binary case, it is also called the population count,]]

History and usage

The Hamming weight is named after the American mathematician Richard Hamming, although he did not originate the notion.

  • In computer chess programs using a bitboard representation, the Hamming weight of a bitboard gives the number of pieces of a given type remaining in the game, or the number of squares of the board controlled by one player's pieces, and is therefore an important contributing term to the value of a position.
  • Hamming weight can be used to efficiently compute find first set using the identity ffs(x) = pop(x ^ (x - 1)). This is useful on platforms such as SPARC that have hardware Hamming weight instructions but no hardware find first set instruction. is one of the fastest that also only needs integer operations.

Minimum weight

In error-correcting coding, the minimum Hamming weight, commonly referred to as the minimum weight w<sub>min</sub> of a code is the weight of the lowest-weight non-zero code word. The weight w of a code word is the number of 1s in the word. For example, the word 11001010 has a weight of 4.

In a linear block code the minimum weight is also the minimum Hamming distance (d<sub>min</sub>) and defines the error correction capability of the code. If w<sub>min</sub>&nbsp;=&nbsp;n, then d<sub>min</sub>&nbsp;=&nbsp;n and the code will correct up to d<sub>min</sub>/2 errors.

Language support

Some C compilers provide intrinsic functions that provide bit counting facilities. For example, GCC (since version 3.4 in April 2004) includes a builtin function <code>__builtin_popcount</code> that will use a processor instruction if available or an efficient library implementation otherwise.

In Common Lisp, the function <code>logcount</code>, given a non-negative integer, returns the number of 1 bits. (For negative integers it returns the number of 0 bits in 2's complement notation.) In either case the integer can be a bignum.

Starting in GHC 7.4, the Haskell base package has a <code>popCount</code> function available on all types that are instances of the <code>Bits</code> class (available from the <code>Data.Bits</code> module).

Further reading

  • (Item 169: Population count assembly code for the PDP/6-10.)
  • Aggregate Magic Algorithms. Optimized population count and other algorithms explained with sample code.
  • Bit Twiddling Hacks Several algorithms with code for counting bits set.
  • Necessary and Sufficient - by Damien Wintour - Has code in C# for various Hamming Weight implementations.
  • Best algorithm to count the number of set bits in a 32-bit integer? - Stackoverflow