Hamming weight

In this binary case, it is also called the population count,[1] popcount, sideways sum,[2] or bit summation.

For processors lacking those features, the best solutions known are based on adding counts in a tree pattern.

If greater memory usage is allowed, we can calculate the Hamming weight faster than the above methods.

With unlimited memory, we could simply create a large lookup table of the Hamming weight of every 64 bit integer.

Muła et al.[13] have shown that a vectorized version of popcount64b can run faster than dedicated instructions (e.g., popcnt on x64 processors).

For example, GCC (since version 3.4 in April 2004) includes a builtin function __builtin_popcount that will use a processor instruction if available or an efficient library implementation otherwise.

In Java, the growable bit-array data structure BitSet has a BitSet.cardinality() method that counts the number of bits that are set.

[17] In Common Lisp, the function logcount, given a non-negative integer, returns the number of 1 bits.

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

A plot of Hamming weight for numbers 0 to 256. [ 4 ]