Hamming weight

Uses your system voice; voice and rate in settings.

Snapshot

≈ 8 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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, popcount, sideways sum, or bit summation.

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, popcount, sideways sum, or bit summation. 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.

The Hamming weight operation can be interpreted as a conversion from the unary numeral system to binary numbers. 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: 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 ones const 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) { x = (x & m1 ) + ((x >> 1) & m1 ); //put count of each 2 bits into those 2 bits x = (x & m2 ) + ((x >> 2) & m2 ); //put count of each 4 bits into those 4 bits x = (x & m4 ) + ((x >> 4) & m4 ); //put count of each 8 bits into those 8 bits x = (x & m8 ) + ((x >> 8) & m8 ); //put count of each 16 bits into those 16 bits x = (x & m16) + ((x >> 16) & m16); //put count of each 32 bits into those 32 bits x = (x & m32) + ((x >> 32) & m32); //put count of each 64 bits into those 64 bits return 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) { x -= (x >> 1) & m1; //put count of each 2 bits into those 2 bits x = (x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits x = (x + (x >> 4)) & m4; //put count of each 8 bits into those 8 bits x += x >> 8; //put count of each 16 bits into their lowest 8 bits x += x >> 16; //put count of each 32 bits into their lowest 8 bits x += x >> 32; //put count of each 64 bits into their lowest 8 bits return x & 0x7f; } //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) { x -= (x >> 1) & m1; //put count of each 2 bits into those 2 bits x = (x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits x = (x + (x >> 4)) & m4; //put count of each 8 bits into those 8 bits return (x * h01) >> 56; //returns left 8 bits of x + (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) { int count; for (count=0; x; count++) x &= x - 1; return count; } Of interest here is the close relationship between Popcount, FFS and CLZ. 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] = { /* bitcounts of integers 0 through 65535, inclusive */ }; //This algorithm uses 3 arithmetic operations and 2 memory reads. int popcount32e(uint32_t x) { return wordbits[x & 0xFFFF] + wordbits[x >> 16]; } //Optionally, the wordbits[] table could be filled using this function int popcount32e_init(void) { uint32_t i; uint16_t x; int count; for (i=0; i A recursive algorithm is given in Donovan & Kernighan /* The weight of i can differ from the weight of i / 2 only in the least significant bit of i */ int popcount32e_init (void) { int i; for (i = 1; sizeof wordbits / sizeof *wordbits > i; ++i) wordbits [i] = wordbits [i >> 1] + (1 & i); } Muła et al. have shown that a vectorized version of popcount64b can run faster than dedicated instructions (e.g., popcnt on x64 processors).

The Harley–Seal algorithm 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 min 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 min ) and defines the error correction capability of the code. If w min  = n, then d min  = n and the code will correct up to d min /2 errors.

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

Text derived from https://en.wikipedia.org/w/index.php?oldid=1340429552 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

15 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.