Hamming weight explained

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 string of bits, this is the number of 1's in the string, 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, popcount, sideways sum, or bit summation.

Examples!String!Hamming weight
111014
111010004
000000000
67801234056710

History and usage

The Hamming weight is named after Richard Hamming although he did not originate the notion. The Hamming weight of binary numbers was already used in 1899 by James W. L. Glaisher to give a formula for the number of odd binomial coefficients in a single row of Pascal's triangle. Irving S. Reed introduced a concept, equivalent to Hamming weight in the binary case, in 1954.

Hamming weight is used in several disciplines including information theory, coding theory, and cryptography. Examples of applications of the Hamming weight include:

Efficient implementation

The population count of a bitstring is often needed in cryptography and other applications. The Hamming distance of two words A and B can be calculated as the Hamming weight of A xor B.

The problem of how to implement it efficiently has been widely studied. A single operation for the calculation, or parallel operations on bit vectors are available on some processors. For processors lacking those features, the best solutions known are based on adding counts in a tree pattern. For example, to count the number of 1 bits in the 16-bit binary number a = 0110 1100 1011 1010, these operations can be done:

ExpressionBinaryDecimalComment
a0110110010111010The original number
b0 = (a >> 0) & 01 01 01 01 01 01 01 0101000100000100001, 0, 1, 0, 0, 1, 0, 0Every other bit from a
b1 = (a >> 1) & 01 01 01 01 01 01 01 0100010100010101010, 1, 1, 0, 1, 1, 1, 1The remaining bits from a
c = b0 + b101011000011001011, 1, 2, 0, 1, 2, 1, 1Count of 1s in each 2-bit slice of a
d0 = (c >> 0) & 0011 0011 0011 001100010000001000011, 0, 2, 1Every other count from c
d2 = (c >> 2) & 0011 0011 0011 001100010010000100011, 2, 1, 1The remaining counts from c
e = d0 + d200100010001100102, 2, 3, 2Count of 1s in each 4-bit slice of a
f0 = (e >> 0) & 00001111 0000111100000010000000102, 2Every other count from e
f4 = (e >> 4) & 00001111 0000111100000010000000112, 3The remaining counts from e
g = f0 + f400000100000001014, 5Count of 1s in each 8-bit slice of a
h0 = (g >> 0) & 000000001111111100000000000001015Every other count from g
h8 = (g >> 8) & 000000001111111100000000000001004The remaining counts from g
i = h0 + h800000000000010019Count of 1s in entire 16-bit word

Here, the operations are as in C programming language, so means to shift X right by Y bits, X & Y means the bitwise AND of X and Y, and + is ordinary addition. The best algorithms known for this problem are based on the concept illustrated above and are given here:

//types and constants used in the functions below//uint64_t is an unsigned 64-bit integer variable type (defined in C99 version of C language)const uint64_t m1 = 0x5555555555555555; //binary: 0101...const uint64_t m2 = 0x3333333333333333; //binary: 00110011..const uint64_t m4 = 0x0f0f0f0f0f0f0f0f; //binary: 4 zeros, 4 ones ...const uint64_t m8 = 0x00ff00ff00ff00ff; //binary: 8 zeros, 8 ones ...const uint64_t m16 = 0x0000ffff0000ffff; //binary: 16 zeros, 16 ones ...const uint64_t m32 = 0x00000000ffffffff; //binary: 32 zeros, 32 onesconst uint64_t h01 = 0x0101010101010101; //the sum of 256 to the power of 0,1,2,3...

//This is a naive implementation, shown for comparison,//and to help in understanding the better functions.//This algorithm uses 24 arithmetic operations (shift, add, and).int popcount64a(uint64_t x)

//This uses fewer arithmetic operations than any other known //implementation on machines with slow multiplication.//This algorithm uses 17 arithmetic operations.int popcount64b(uint64_t x)

//This uses fewer arithmetic operations than any other known //implementation on machines with fast multiplication.//This algorithm uses 12 arithmetic operations, one of which is a multiply.int popcount64c(uint64_t x)

The above implementations have the best worst-case behavior of any known algorithm. However, when a value is expected to have few nonzero bits, it may instead be more efficient to use algorithms that count these bits one at a time. As Wegner described in 1960, the bitwise AND of x with x - 1 differs from x only in zeroing out the least significant nonzero bit: subtracting 1 changes the rightmost string of 0s to 1s, and changes the rightmost 1 to a 0. If x originally had n bits that were 1, then after only n iterations of this operation, x will be reduced to zero. The following implementation is based on this principle.

//This is better when most bits in x are 0//This algorithm works the same for all data sizes.//This algorithm uses 3 arithmetic operations and 1 comparison/branch per "1" bit in x.int popcount64d(uint64_t x)

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. If we can store a lookup table of the hamming function of every 16 bit integer, we can do the following to compute the Hamming weight of every 32 bit integer.static uint8_t wordbits[65536] = ;//This algorithm uses 3 arithmetic operations and 2 memory reads.int popcount32e(uint32_t x)

//Optionally, the wordbits[] table could be filled using this functionint popcount32e_init(void)

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

Minimum weight

In error-correcting coding, the minimum Hamming weight, commonly referred to as the minimum weight wmin 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 (dmin) and defines the error correction capability of the code. If wmin = n, then dmin = n and the code will correct up to dmin/2 errors.[1]

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 __builtin_popcount that will use a processor instruction if available or an efficient library implementation otherwise. LLVM-GCC has included this function since version 1.5 in June 2005.

In the C++ Standard Library, the bit-array data structure bitset has a count method that counts the number of bits that are set. In C++20, a new header <bit> was added, containing functions std::popcount and std::has_single_bit, taking arguments of unsigned integer types.

In Java, the growable bit-array data structure has a method that counts the number of bits that are set. In addition, there are and functions to count bits in primitive 32-bit and 64-bit integers, respectively. Also, the arbitrary-precision integer class also has a method that counts bits.

In Python, the int type has a bit_count method to count the number of bits set. This functionality was introduced in Python 3.10, released in October 2021.[2]

In Common Lisp, the function logcount, 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 popCount function available on all types that are instances of the Bits class (available from the Data.Bits module).

MySQL version of SQL language provides BIT_COUNT as a standard function.

Fortran 2008 has the standard, intrinsic, elemental function popcnt returning the number of nonzero bits within an integer (or integer array).

Some programmable scientific pocket calculators feature special commands to calculate the number of set bits, e.g. #B on the HP-16C and WP 43S, #BITS or BITSUM on HP-16C emulators, and nBITS on the WP 34S.

FreePascal implements popcnt since version 3.0.

Processor support

See also

Further reading

External links

Notes and References

  1. Stern & Mahmoud, Communications System Design, Prentice Hall, 2004, p 477ff.
  2. Web site: What's New In Python 3.10 . python.org.