Hamming weight

Hamming weight

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. In this binary case, it is also called the population count, or popcount.

Examples

Subtracting 1 changes the rightmost string of 0s to 1s, and changes the rightmost 1 to a 0. The AND then removes that rightmost 1. 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 are based on this principle.

//This is better when most bits in x are 0//It uses 3 arithmetic operations and one comparison/branch per "1" bit in x.int popcount_4(uint64 x) { uint64 count; for (count=0; x; count++) x &= x-1; return count;}

//This is better if most bits in x are 0.//It uses 2 arithmetic operations and one comparison/branch per "1" bit in x.//It is the same as the previous function, but with the loop unrolled.
#define f(y) if ((x &= x-1) = 0) return y;int popcount_5(uint64 x) { if (x = 0) return 0; f( 1) f( 2) f( 3) f( 4) f( 5) f( 6) f( 7) f( 8) f( 9) f(10) f(11) f(12) f(13) f(14) f(15) f(16) f(17) f(18) f(19) f(20) f(21) f(22) f(23) f(24) f(25) f(26) f(27) f(28) f(29) f(30) f(31) f(32) f(33) f(34) f(35) f(36) f(37) f(38) f(39) f(40) f(41) f(42) f(43) f(44) f(45) f(46) f(47) f(48) f(49) f(50) f(51) f(52) f(53) f(54) f(55) f(56) f(57) f(58) f(59) f(60) f(61) f(62) f(63) return 64;}

//Use this instead if most bits in x are 1 instead of 0
#define f(y) if ((x |= x+1) = hff) return 64-y;

Language Support

In C++ STL, the bit-array data structure bitset has a count() method that counts the number of bits that are set.

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 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.

See also

*Hamming distance
*Minimum weight

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://www.inwap.com/pdp10/hbaker/hakmem/hacks.html#item169 HACKMEM item 169] . Population count assembly code for the PDP/6-10.
* [http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive Bit Twiddling Hacks] Several algorithms with code for counting bits set.


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Hamming distance — 3 bit binary cube for finding Hamming distance …   Wikipedia

  • Weight (strings) — The a weight of a string, for a a letter, is the number of times that letter occurs in the string. More precisely, let A be a finite set (called the alphabet ), ain A a letter of A, and cin A^* a string (where A^* is the free monoid generated by… …   Wikipedia

  • Hamming-Abstand — Der Hamming Abstand, die Hamming Distanz und das Hamming Gewicht, benannt nach dem US amerikanischen Mathematiker Richard Wesley Hamming (1915–1998), sind Maße für die Unterschiedlichkeit von Zeichenketten. Der Hamming Abstand zweier Blöcke mit… …   Deutsch Wikipedia

  • Hamming-Distanz — Der Hamming Abstand, die Hamming Distanz und das Hamming Gewicht, benannt nach dem US amerikanischen Mathematiker Richard Wesley Hamming (1915–1998), sind Maße für die Unterschiedlichkeit von Zeichenketten. Häufig handelt es sich um binär… …   Deutsch Wikipedia

  • Hamming-Gewicht — Der Hamming Abstand, die Hamming Distanz und das Hamming Gewicht, benannt nach dem US amerikanischen Mathematiker Richard Wesley Hamming (1915–1998), sind Maße für die Unterschiedlichkeit von Zeichenketten. Häufig handelt es sich um binär… …   Deutsch Wikipedia

  • Hamming Abstand — Der Hamming Abstand, die Hamming Distanz und das Hamming Gewicht, benannt nach dem US amerikanischen Mathematiker Richard Wesley Hamming (1915–1998), sind Maße für die Unterschiedlichkeit von Zeichenketten. Häufig handelt es sich um binär… …   Deutsch Wikipedia

  • Constant-weight code — In coding theory, a constant weight code, also called an m of n code, is an error detection and correction code where all codewords share the same Hamming weight. The theory is closely connected to that of designs (such as t designs and Steiner… …   Wikipedia

  • 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 code word. The weight w of a code word is the number of 1s in the word. For example the word… …   Wikipedia

  • Coding theory approaches to nucleic acid design — DNA code construction refers to the application of coding theory to the design of nucleic acid systems for the field of DNA–based computation. Contents 1 Introduction 2 Definitions 2.1 Property U 2 …   Wikipedia

  • Distributed source coding — (DSC) is an important problem in information theory and communication. DSC problems regard the compression of multiple correlated information sources that do not communicate with each other.[1] By modeling the correlation between multiple sources …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”