Editing Hamming weight

{{Short description|Number of nonzero symbols in a string}}
{{redirect|popcnt|The CPU instruction|SSE4#POPCNT_and_LZCNT}}
{{Use dmy dates|date=May 2019|cs1-dates=y}}
The '''Hamming weight''' of a [[string (computer science)|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 [[bit]]s, this is the number of bits set to 1, or the [[digit sum]] of the [[Binary numeral system|binary representation]] of a given number and the [[Taxicab geometry|''ℓ''₁ norm]] of a bit vector. In this binary case, it is also called the '''population count''',<ref name="Warren_2013"/> '''popcount''', '''sideways sum''',<ref name="Knuth_2009"/> or '''bit summation'''.<ref name="HP-16C_1982"/>
 
{|class="wikitable" align="right"
|+Examples
!String
!Hamming weight
|-
|'''111'''0'''1'''
|4
|-
|'''111'''0'''1'''000
|4
|-
|00000000
|0
|-
|'''678'''0'''1234'''0'''567'''
|10
|}

[[File:Hamming weight plot.png|thumb|right|A plot of Hamming weight for numbers 0 to 256.<ref name="formulae">{{cite web |url=https://formulae.org/?script=examples/Population_count |title=Population count the Fōrmulæ programming language |first=Laurence |last = R.Ugalde |website=Fōrmulæ |access-date=June 2, 2024}}</ref>]]

== History and usage ==
The Hamming weight is named after the American mathematician [[Richard Hamming]], although he did not originate the notion.<ref name="Thompson_1983"/> The Hamming weight of binary numbers was already used in 1899 by [[James Whitbread Lee Glaisher|James W. L. Glaisher]] to give a formula for [[Gould's sequence|the number of odd binomial coefficients]] in a single row of [[Pascal's triangle]].<ref name="Glaisher_1899"/> [[Irving S. Reed]] introduced a concept, equivalent to Hamming weight in the binary case, in 1954.<ref name="Reed_1954"/>

Hamming weight is used in several disciplines including [[information theory]], [[coding theory]], and [[cryptography]]. Examples of applications of the Hamming weight include:
* In modular [[exponentiation by squaring]], the number of modular multiplications required for an exponent ''e'' is log<sub>2</sub> ''e'' + weight(''e''). This is the reason that the public key value ''e'' used in [[RSA (algorithm)|RSA]] is typically chosen to be a number of low Hamming weight.<ref name="CLNZ"/>
* The Hamming weight determines path lengths between nodes in [[Chord (distributed hash table)|Chord distributed hash tables]].<ref name="Stoica_2003"/>
* [[IrisCode]] lookups in biometric databases are typically implemented by calculating the [[Hamming distance]] to each stored record.<ref>{{cite journal
 | last1 = Kong | first1 = A.W.K.
 | last2 = Zhang | first2 = D.
 | last3 = Kamel | first3 = M.S.
 | date = February 2010
 | doi = 10.1109/tip.2009.2033427
 | issue = 2
 | journal = IEEE Transactions on Image Processing
 | pages = 522–532
 | title = An analysis of IrisCode
 | volume = 19}}</ref>
* 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.<ref>{{cite journal
 | last = Heinz | first = E.A.
 | date = September 1997
 | doi = 10.3233/icg-1997-20304
 | issue = 3
 | journal = ICGA Journal
 | pages = 166–176
 | title = How Darkthought plays chess
 | volume = 20}} Updated and reprinted in ''Scalable Search in Computer Chess'' (Vieweg+Teubner Verlag, 2000), pp. 185–198, {{doi|10.1007/978-3-322-90178-1_13}}</ref>
* 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.<ref name="SPARC_1992"/><ref name="Warren_2013"/>
* The Hamming weight operation can be interpreted as a conversion from the [[unary numeral system]] to [[binary number]]s.<ref name="Blaxell_1978"/>

== Efficient implementation ==
The population count of a [[bit array|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''.<ref name="Warren_2013"/>

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 [[#Processor support|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&nbsp;=&nbsp;0110&nbsp;1100&nbsp;1011&nbsp;1010, these operations can be done:

{| class="wikitable" style="text-align:center;"
! Expression
! colspan=8 | Binary
! Decimal
! Comment
|-
| style="text-align:left;" | <code>a</code>
| 01
| 10
| 11
| 00
| 10
| 11
| 10
| 10
| style="text-align:left;"   {{n/a|27834}}
| style="text-align:left;" | The original number
|-
| style="text-align:left;" | <code>b0 = (a >> 0) & 01 01 01 01 01 01 01 01</code>
| 01
| 00
| 01
| 00
| 00
| 01
| 00
| 00
| style="text-align:left;" | 1, 0, 1, 0, 0, 1, 0, 0
| style="text-align:left;" | Every other bit from a
|-
| style="text-align:left;" | <code>b1 = (a >> 1) & 01 01 01 01 01 01 01 01</code>
| 00
| 01
| 01
| 00
| 01
| 01
| 01
| 01
| style="text-align:left;" | 0, 1, 1, 0, 1, 1, 1, 1
| style="text-align:left;" | The remaining bits from a
|-
| style="text-align:left;" | <code>c = b0 + b1</code>
| 01
| 01
| 10
| 00
| 01
| 10
| 01
| 01
| style="text-align:left;" | 1, 1, 2, 0, 1, 2, 1, 1
| style="text-align:left;" | Count of 1s in each 2-bit slice of a
|-
| style="text-align:left;" | <code>d0 = (c >> 0) & 0011 0011 0011 0011</code>
| colspan=2 | 0001
| colspan=2 | 0000
| colspan=2 | 0010
| colspan=2 | 0001
| style="text-align:left;" | 1, 0, 2, 1
| style="text-align:left;" | Every other count from c
|-
| style="text-align:left;" | <code>d2 = (c >> 2) & 0011 0011 0011 0011</code>
| colspan=2 | 0001
| colspan=2 | 0010
| colspan=2 | 0001
| colspan=2 | 0001
| style="text-align:left;" | 1, 2, 1, 1
| style="text-align:left;" | The remaining counts from c
|-
| style="text-align:left;" | <code>e = d0 + d2</code>
| colspan=2 | 0010
| colspan=2 | 0010
| colspan=2 | 0011
| colspan=2 | 0010
| style="text-align:left;" | 2, 2, 3, 2
| style="text-align:left;" | Count of 1s in each 4-bit slice of a
|-
| style="text-align:left;" | <code>f0 = (e >> 0) & 00001111  00001111</code>
| colspan=4 | 00000010
| colspan=4 | 00000010
| style="text-align:left;" | 2, 2
| style="text-align:left;" | Every other count from e
|-
| style="text-align:left;" | <code>f4 = (e >> 4) & 00001111 00001111</code>
| colspan=4 | 00000010
| colspan=4 | 00000011
| style="text-align:left;" | 2, 3
| style="text-align:left;" | The remaining counts from e
|-
| style="text-align:left;" | <code>g = f0 + f4</code>
| colspan=4 | 00000100
| colspan=4 | 00000101
| style="text-align:left;" | 4, 5
| style="text-align:left;" | Count of 1s in each 8-bit slice of a
|-
| style="text-align:left;" | <code>h0 = (g >> 0) & 0000000011111111</code>
| colspan=8 | 0000000000000101
| style="text-align:left;" | 5
| style="text-align:left;" | Every other count from g
|-
| style="text-align:left;" | <code>h8 = (g >> 8) & 0000000011111111</code>
| colspan=8 | 0000000000000100
| style="text-align:left;" | 4
| style="text-align:left;" | The remaining counts from g
|-
| style="text-align:left;" | <code>i = h0 + h8</code>
| colspan=8 | 0000000000001001
| style="text-align:left;" | 9
| style="text-align:left;" | Count of 1s in entire 16-bit word
|}

Here, the operations are as in [[C (programming language)|C programming language]], so {{code|X >> Y}} 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:<ref name="Warren_2013"/>

<syntaxhighlight lang="c">
//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<<8) + (x<<16) + (x<<24) + ... 
}
</syntaxhighlight>

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,<ref name="Wegner_1960"/> the [[bitwise AND]] of ''x'' with ''x''&nbsp;&minus;&nbsp;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.

<syntaxhighlight lang="c">
//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;
}
</syntaxhighlight>

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.
<syntaxhighlight lang="c">
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];
}
</syntaxhighlight>

<syntaxhighlight lang="c">
//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 <= 0xFFFF; i++)
    {
        x = i;
        for (count=0; x; count++) // borrowed from popcount64d() above
            x &= x - 1;
        wordbits[i] = count;
    }
}
</syntaxhighlight>

A recursive algorithm is given in Donovan & Kernighan<ref name="Donovan_2016" />
<syntaxhighlight lang="c">
/* 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);
}
</syntaxhighlight>

Muła et al.<ref name="Mula_2018"/> 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 code|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.<ref>Stern & Mahmoud, ''Communications System Design'', [[Prentice Hall]], 2004, p&nbsp;477ff.</ref>

== Language support ==
Some C compilers provide intrinsic functions that provide bit counting facilities. For example, [[GNU Compiler Collection|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.<ref name="GCC"/> [[LLVM|LLVM-GCC]] has included this function since version 1.5 in June 2005.<ref name="LLVM"/>

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

In Java, the growable bit-array data structure {{Javadoc:SE|java/util|BitSet}} has a {{Javadoc:SE|java/util|BitSet|cardinality()}} method that counts the number of bits that are set. In addition, there are {{Javadoc:SE|java/lang|Integer|bitCount(int)}} and {{Javadoc:SE|java/lang|Long|bitCount(long)}} functions to count bits in primitive 32-bit and 64-bit integers, respectively. Also, the {{Javadoc:SE|java/math|BigInteger}} arbitrary-precision integer class also has a {{Javadoc:SE|java/math|BigInteger|bitCount()}} method that counts bits.

In [[Python (programming language)|Python]], the <code>int</code> type has a <code>bit_count()</code> method to count the number of bits set. This functionality was introduced in Python 3.10, released in October 2021.<ref>{{cite web |title=What's New In Python 3.10 |url=https://docs.python.org/3.10/whatsnew/3.10.html |website=python.org}}</ref>

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 [[Glasgow Haskell Compiler|GHC]] 7.4, the [[Haskell (programming language)|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).<ref name="GHC"/>

[[MySQL]] version of [[SQL]] language provides <code>BIT_COUNT()</code> as a standard function.<ref name="MySQL_50"/>

[[Fortran 2008]] has the standard, intrinsic, elemental function <code>popcnt</code> returning the number of nonzero bits within an integer (or integer array).<ref name="Metcalf_2011"/>

Some programmable scientific pocket calculators feature special commands to calculate the number of set bits, e.g. <code>#B</code> on the [[HP-16C]]<ref name="HP-16C_1982"/><ref name="Schwartz_Grevelle_2003"/> and [[WP&nbsp;43S]],<ref name="Bonin_2019_OG"/><ref name="Bonin_2019_RG"/> <code>#BITS</code><ref name="Martin_McClure_2015"/><ref name="Martin_2015"/> or <code>BITSUM</code><ref name="Thörngren_2017"/><ref name="Thörngren_2017_2"/> on HP-16C emulators, and <code>nBITS</code> on the [[WP&nbsp;34S]].<ref name="Bonin_2012"/><ref name="Bonin_2015"/>

[[FreePascal]] implements popcnt since version 3.0.<ref name="FPC docs"/>

== Processor support ==
* The [[IBM STRETCH]] computer in the 1960s calculated the number of set bits as well as the [[number of leading zeros]] as a by-product of all logical operations.<ref name="Warren_2013"/>
* [[Cray]] supercomputers early on featured a population count [[machine instruction]], rumoured to have been specifically requested by the U.S. government [[National Security Agency]] for [[cryptanalysis]] applications.<ref name="Warren_2013"/><!-- This ref supports the rumour in general, but does not mention Cray -->
* [[Control Data Corporation]]'s (CDC) [[CDC 6000 series|6000]] and [[CDC Cyber|Cyber 70/170]] series machines included a population count instruction; in [[COMPASS#COMPASS for 60-bit machines|COMPASS]], this instruction was coded as <code>CXi</code>.
* The 64-bit [[SPARC]] version 9 architecture defines a <code>POPC</code> instruction,<ref name="SPARC_1992"/><ref name="Warren_2013"/> but most implementations do not implement it, requiring it be emulated by the operating system.<ref name="JDK_BitCount"/>
* [[Donald Knuth]]'s model computer [[MMIX]] that is going to replace [[MIX (abstract machine)|MIX]] in his book [[The Art of Computer Programming]] has an <code>SADD</code> instruction since 1999. <code>SADD a,b,c</code> counts all bits that are 1 in b and 0 in c and writes the result to a.
* [[Compaq]]'s [[Alpha 21264A]], released in 1999, was the first Alpha series CPU design that had the count extension (<code>CIX</code>).
* [[Analog Devices]]' [[Blackfin]] processors feature the <code>ONES</code> instruction to perform a 32-bit population count.<ref name="AD_2001"/>
* [[AMD]]'s [[AMD K10|Barcelona]] architecture introduced the advanced bit manipulation (ABM) [[Instruction set|ISA]] introducing the <code>POPCNT</code> instruction as part of the [[SSE4a]] extensions in 2007.
* [[Intel Core]] processors introduced a <code>POPCNT</code> instruction with the [[SSE4.2]] [[instruction set]] extension, first available in a [[Nehalem (microarchitecture)|Nehalem]]-based [[Core i7]] processor, released in November 2008.
* The [[ARM architecture]] introduced the <code>VCNT</code> instruction as part of the [[ARM Advanced SIMD|Advanced SIMD]] ([[NEON (instruction set)|NEON]]) extensions.
* The [[RISC-V]] architecture introduced the <code>CPOP</code> instruction as part of the Bit Manipulation (B) extension.<ref name="RISC-V-B"/>

== See also ==
* [[Two's complement]]
* [[Fan out]]

==References==
{{Reflist|refs=
<ref name="CLNZ">{{cite conference
 | last1 = Cohen | first1 = Gérard D. | author1-link = Gérard Denis Cohen
 | last2 = Lobstein | first2 = Antoine
 | last3 = Naccache | first3 = David
 | last4 = Zémor | first4 = Gilles
 | editor-last = Nyberg | editor-first = Kaisa
 | contribution = How to improve an exponentiation black-box
 | doi = 10.1007/BFb0054128
 | pages = 211–220
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = Advances in Cryptology – EUROCRYPT '98, International Conference on the Theory and Application of Cryptographic Techniques, Espoo, Finland, May 31 – June 4, 1998, Proceeding
 | volume = 1403
 | year = 1998| doi-access = free
 | isbn = 978-3-540-64518-4 }}</ref>
<ref name="Knuth_2009">{{cite book |author-first=Donald Ervin |author-last=Knuth |author-link=Donald Ervin Knuth |title=The Art of Computer Programming |title-link=The Art of Computer Programming |volume=4, Fascicle 1 |chapter=Bitwise tricks & techniques; Binary Decision Diagrams |publisher=[[Addison–Wesley Professional]] |isbn=978-0-321-58050-4 |date=2009}} (NB. Draft of [http://www-cs-faculty.stanford.edu/~knuth/fasc1b.ps.gz Fascicle 1b] {{Webarchive|url=https://web.archive.org/web/20160312073634/http://www-cs-faculty.stanford.edu/~knuth/fasc1b.ps.gz |date=2016-03-12  }} available for download.)</ref>
<ref name="Warren_2013">{{cite book |title=Hacker's Delight |title-link=Hacker's Delight |author-first=Henry S. |author-last=Warren Jr. |date=2013 |orig-year=2002 |edition=2 |publisher=[[Addison Wesley]] - [[Pearson Education, Inc.]] |isbn=978-0-321-84268-8 |id=0-321-84268-5 |pages=81–96}}</ref>
<ref name="Stoica_2003">{{cite journal |author-last1=Stoica |author-first1=I. |author-last2=Morris |author-first2=R. |author-last3=Liben-Nowell |author-first3=D. |author-last4=Karger |author-first4=D. R. |author-last5=Kaashoek |author-first5=M. F. |author-last6=Dabek |author-first6=F. |author-last7=Balakrishnan |author-first7=H. |title=Chord: a scalable peer-to-peer lookup protocol for internet applications |journal=[[IEEE/ACM Transactions on Networking]] |volume=11 |issue=1 |date=February 2003 |pages=17–32 |doi=10.1109/TNET.2002.808407 |s2cid=221276912 |quote=Section 6.3: "In general, the number of fingers we need to follow will be the number of ones in the binary representation of the distance from node to query."}}</ref>
<ref name="Blaxell_1978">{{cite journal |author-last=Blaxell |author-first=David |editor-last1=Hogben |editor-first1=David |editor-last2=Fife |editor-first2=Dennis W. |title=Record linkage by bit pattern matching |pages=146–156 |publisher=[[U.S. Department of Commerce]] / [[National Bureau of Standards]] |series=NBS Special Publication |journal=Computer Science and Statistics--Tenth Annual Symposium on the Interface |url=https://books.google.com/books?id=-MrJPUqTPh8C&pg=PA146 |volume=503 |date=1978}}</ref>
<ref name="Wegner_1960">{{cite journal |author-last=Wegner |author-first=Peter <!-- A.? according to Hacker's Delight --> |author-link=Peter Wegner (computer scientist)|doi=10.1145/367236.367286 |issue=5 |journal=[[Communications of the ACM]] |page=322 |title=A technique for counting ones in a binary computer |volume=3 |date=May 1960|s2cid=31683715 |doi-access=free }}</ref>
<ref name="GCC">{{cite web |url=https://gcc.gnu.org/gcc-3.4/changes.html |title=GCC 3.4 Release Notes |work=GNU Project}}</ref>
<ref name="LLVM">{{cite web |url=http://llvm.org/releases/1.5/docs/ReleaseNotes.html |title=LLVM 1.5 Release Notes |work=LLVM Project}}</ref>
<ref name="Glaisher_1899">{{cite journal |author-last=Glaisher |author-first=James Whitbread Lee |author-link=James Whitbread Lee Glaisher |journal=[[The Quarterly Journal of Pure and Applied Mathematics]] |pages=150–156 |title=On the residue of a binomial-theorem coefficient with respect to a prime modulus |url=https://books.google.com/books?id=j7sKAAAAIAAJ&pg=PA150 |volume=30 |date=1899}} (NB. See in particular the final paragraph of p.&nbsp;156.)</ref>
<ref name="Thompson_1983">{{cite book |author-first=Thomas M. |author-last=Thompson |title=From Error-Correcting Codes through Sphere Packings to Simple Groups |publisher=[[The Mathematical Association of America]] |series=The Carus Mathematical Monographs #21 |date=1983 |page=33}}</ref>
<ref name="Reed_1954">{{cite journal |author-first=Irving Stoy |author-last=Reed |author-link=Irving Stoy Reed |title=A Class of Multiple-Error-Correcting Codes and the Decoding Scheme |journal=[[IRE Professional Group on Information Theory]] |publisher=[[Institute of Radio Engineers]] (IRE) |volume=PGIT-4 |date=1954 |pages=38–49}}</ref>
<ref name="GHC">{{cite web |url=http://www.haskell.org/ghc/docs/7.4-latest/html/users_guide/release-7-4-1.html#id527862 |title=GHC 7.4.1 release notes}} GHC documentation.</ref>
<ref name="MySQL_50">{{cite web |url=https://dev.mysql.com/doc/refman/5.0/en/bit-functions.html |title=Chapter 12.11. Bit Functions — MySQL 5.0 Reference Manual}}</ref>
<ref name="Metcalf_2011">{{cite book |author-first1=Michael |author-last1=Metcalf |author-first2=John |author-last2=Reid |author-first3=Malcolm |author-last3=Cohen |date=2011 |title=Modern Fortran Explained |publisher=[[Oxford University Press]] |isbn=978-0-19-960142-4 |page=380}}</ref>
<ref name="SPARC_1992">{{cite book |author=SPARC International, Inc. |title=The SPARC architecture manual: version 8 |date=1992 |publisher=[[Prentice Hall]] |location=Englewood Cliffs, New Jersey, USA |isbn=0-13-825001-4 |pages=[https://archive.org/details/sparcarchitectur00spar/page/231 231] |chapter-url=https://archive.org/details/sparcarchitectur00spar/page/231 |edition=Version 8 |chapter=A.41: Population Count. Programming Note |chapter-url-access=registration}}</ref>
<ref name="HP-16C_1982">{{cite book |title=Hewlett-Packard HP-16C Computer Scientist Owner's Handbook |publisher=[[Hewlett-Packard Company]] |date=April 1982 |id=00016-90001 |url=http://www.hp41.net/forum/fileshp41net/hp16c.pdf<!-- https://www.scss.tcd.ie/SCSSTreasuresCatalog/hardware/TCD-SCSS-T.20160121.004/HP16C-OwnersHandbook.pdf --> |access-date=2017-03-28 |url-status=live |archive-url=https://web.archive.org/web/20170328204119/http://www.hp41.net/forum/fileshp41net/hp16c.pdf<!-- https://web.archive.org/web/20170328201815/https://www.scss.tcd.ie/SCSSTreasuresCatalog/hardware/TCD-SCSS-T.20160121.004/HP16C-OwnersHandbook.pdf --> |archive-date=2017-03-28}}</ref>
<ref name="Schwartz_Grevelle_2003">{{cite book |title=HP16C Emulator Library for the HP48S/SX |author-first1=Jake |author-last1=Schwartz |author-first2=Rick |author-last2=Grevelle |date=2003-10-20 |orig-year=1993<!-- 1993-04 --> |edition=1 |version=1.20 |url=http://www.pahhc.org/mul8r.htm |access-date=2015-08-15}} (NB. This library also works on the [[HP 48G]]/[[HP 48GX|GX]]/[[HP 48G+|G+]]. Beyond the feature set of the [[HP-16C]] this package also supports calculations for binary, octal, and hexadecimal [[floating-point number]]s in [[scientific notation]] in addition to the usual decimal floating-point numbers.)</ref>
<ref name="Martin_McClure_2015">{{cite web |title=HP16C Emulator Module for the HP-41CX - User's Manual and QRG |author-first1=Ángel M. |author-last1=Martin |author-first2=Greg J. |author-last2=McClure |date=2015-09-05 |url=http://systemyde.com/pdf/HP_16C_Emulator_Manual.pdf |access-date=2017-04-27 |url-status=live |archive-url=https://web.archive.org/web/20170427204416/http://systemyde.com/pdf/HP_16C_Emulator_Manual.pdf |archive-date=2017-04-27}} (NB. Beyond the [[HP-16C]] feature set this custom library for the [[HP-41CX]] extends the functionality of the calculator by about 50 additional functions.)</ref>
<ref name="Martin_2015">{{cite web |title=HP-41: New HP-16C Emulator available |author-first=Ángel M. |author-last=Martin |date=2015-09-07 |url=http://www.hpmuseum.org/forum/thread-4663.html |access-date=2017-04-27 |url-status=live |archive-url=https://web.archive.org/web/20170427204721/http://www.hpmuseum.org/forum/thread-4663.html |archive-date=2017-04-27}}</ref>
<ref name="Thörngren_2017">{{cite web |author-first=Håkan |author-last=Thörngren |title=Ladybug Documentation |edition=release 0A |date=2017-01-10 |url=http://www.hpmuseum.org/forum/attachment.php?aid=4350 |access-date=2017-01-29}} [http://www.hpmuseum.org/forum/attachment.php?aid=4349]</ref>
<ref name="Thörngren_2017_2">{{cite web |title=New HP-41 module available: Ladybug |date=2017-01-10 |url=http://www.hpmuseum.org/forum/thread-7545.html |access-date=2017-01-29 |url-status=live |archive-url=https://web.archive.org/web/20170129182549/http://www.hpmuseum.org/forum/thread-7545.html |archive-date=2017-01-29}}</ref>
<ref name="Bonin_2012">{{cite web |author-first1=Paul |author-last1=Dale |author-first2=Walter |author-last2=Bonin |edition=3.1 |title=WP 34S Owner's Manual |date=2012 |orig-year=2008 |url=https://freefr.dl.sourceforge.net/project/wp34s/doc/Manual_wp_34s_3_1.pdf |access-date=2017-04-27}}</ref>
<ref name="Bonin_2015">{{cite book |author-first=Walter |author-last=Bonin |edition=3.3 |title=WP 34S Owner's Manual |date=2015 |publisher=CreateSpace Independent Publishing Platform |orig-year=2008 |isbn=978-1-5078-9107-0}}</ref>
<ref name="AD_2001">{{cite book |title=Blackfin Instruction Set Reference |date=2001 |publisher=[[Analog Devices]] |edition=Preliminary |pages=8–24 |id=Part Number 82-000410-14}}</ref> 
<ref name="Donovan_2016">{{cite book |author-first1=Alan |author-last1=Donovan |author-first2=Brian |author-last2=Kernighan |title=The Go Programming Language |date=2016 |publisher=Addison-Weseley |isbn=978-0-13-419044-0}}</ref>
<ref name="Mula_2018">{{cite journal |author-last1=Muła |author-first1=Wojciech |author-last2=Kurz |author-first2=Nathan |author-last3=Lemire |author-first3=Daniel |title=Faster Population Counts Using AVX2 Instructions |journal=[[Computer Journal]] |volume=61 |issue=1| date=January 2018 |pages=111–120 |doi=10.1093/comjnl/bxx046 |arxiv=1611.07612|s2cid=540973 }}</ref>
<ref name="Bonin_2019_OG">{{cite book |title=WP&nbsp;43S Owner's Manual |date=2019 |orig-year=2015 |author-last=Bonin |author-first=Walter |isbn=978-1-72950098-9 |edition=draft |version=0.12 |page=135 |url=https://gitlab.com/Over_score/wp43s/raw/master/draft%20documentation/Owner_wp_43s_0_12s.pdf?inline=false |access-date=2019-08-05 }}{{Dead link|date=April 2024 |bot=InternetArchiveBot |fix-attempted=yes }} [https://gitlab.com/Over_score/wp43s] [https://sourceforge.net/projects/wp43s/] (314 pages)</ref>
<ref name="Bonin_2019_RG">{{cite book |title=WP&nbsp;43S Reference Manual |date=2019 |orig-year=2015 |author-last=Bonin |author-first=Walter |isbn=978-1-72950106-1 |edition=draft |version=0.12 |pages=xiii, 104, 115, 120, 188 |url=https://gitlab.com/Over_score/wp43s/raw/master/draft%20documentation/Reference_wp_43s_0_12s.pdf?inline=false |access-date=2019-08-05 }}{{Dead link|date=April 2024 |bot=InternetArchiveBot |fix-attempted=yes }} [https://gitlab.com/Over_score/wp43s] [https://sourceforge.net/projects/wp43s/] (271 pages)</ref>
<ref name="FPC docs">{{cite web |title=Free Pascal documentation popcnt |url=https://www.freepascal.org/docs-html/rtl/system/popcnt.html |access-date=2019-12-07 }}</ref>
<ref name="JDK_BitCount">{{cite web |title=JDK-6378821: bitCount() should use POPC on SPARC processors and AMD+10h |date=2006-01-30 |website=Java bug database |url=https://bugs.java.com/bugdatabase/view_bug.do?bug_id=6378821}}</ref>
<ref name="RISC-V-B">{{cite web |title=RISC-V "B" Bit Manipulation Extension for RISC-V, Draft v0.37 |date=2019-03-22 |author-last=Wolf |author-first=Claire |website=Github |url=https://github.com/riscv/riscv-bitmanip/blob/master/bitmanip-draft.pdf}}</ref>
}}

==Further reading==
* {{cite book |title=HAKMEM |title-link=HAKMEM |author-first1=Michael |author-last1=Beeler |author-first2=Ralph William |author-last2=Gosper |author-link2=Bill Gosper |author-first3=Richard C. |author-last3=Schroeppel |author-link3=Richard C. Schroeppel |contribution=compilation |contributor-first1=Richard C. |contributor-last1=Schroeppel |contributor-link1=Richard C. Schroeppel |contributor-last2=Orman |contributor-first2=Hilarie K. |date=1972-02-29 |publisher=[[MIT AI Lab|Artificial Intelligence Laboratory]], [[Massachusetts Institute of Technology]], Cambridge, Massachusetts, USA |id=MIT AI Memo 239 |type=report}} ([http://www.inwap.com/pdp10/hbaker/hakmem/hacks.html#item169 Item 169]: Population count assembly code for the PDP/6-10.)

==External links==
* [http://aggregate.ee.engr.uky.edu/MAGIC/#Population%20Count%20(Ones%20Count) Aggregate Magic Algorithms]. Optimized population count and other algorithms explained with sample code.
* [http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive Bit Twiddling Hacks] Several algorithms with code for counting bits set.
* [http://www.necessaryandsufficient.net/2009/04/optimising-bit-counting-using-iterative-data-driven-development Necessary and Sufficient] {{Webarchive|url=https://web.archive.org/web/20170923043212/http://www.necessaryandsufficient.net/2009/04/optimising-bit-counting-using-iterative-data-driven-development/ |date=2017-09-23  }} - by Damien Wintour - Has code in C# for various Hamming Weight implementations.
* [https://stackoverflow.com/questions/109023/best-algorithm-to-count-the-number-of-set-bits-in-a-32-bit-integer/ Best algorithm to count the number of set bits in a 32-bit integer?] - Stackoverflow

{{DEFAULTSORT:Hamming Weight}}
[[Category:Coding theory]]
[[Category:Articles with example C code]]