| Graphische Darstellung des Hamming-Gewichts der Zahlen von 0 bis 256 in Binärdarstellung. |
Das Hamming-Gewicht einer Zeichenkette ist definiert als die Anzahl der vom Nullzeichen des verwendeten Alphabets verschiedenen Zeichen. Es ist äquivalent mit dem Hamming-Abstand zum Nullvektor (einer gleich langen Zeichenkette, die nur aus Nullzeichen besteht). Für den klassischen Fall einer binären Zeichenfolge ist dies die Anzahl der gesetzten Bits dieser Zeichenfolge und wird auch population count oder popcount genannt und kann als die Ziffernsumme der binären Darstellung einer gegebenen Zahl bzw. als die ℓ₁-Norm eines Bitvektors verstanden werden.
Das Hamming-Gewicht ist benannt nach Richard Hamming, obwohl dieser den Begriff nicht prägte. Im Zusammenhang mit binären Zahlen wurde er bereits 1899 von J. W. L. Glaisher verwendet, um eine Formel für die Anzahl der ungeraden Binomialkoeffizienten in einer einzelnen Reihe des Pascalschen Dreiecks anzugeben. Und Irving S. Reed führte 1954 ein Konzept ein, das dem Hamming-Gewicht für binäre Zahlen ähnlich ist.
Das Hamming-Gewicht wird unter anderem in der Informationstheorie, der Kodierungstheorie und der Kryptographie verwendet. Beispiele für Anwendungen des Hamming-Gewichts sind:
Das Hamming-Gewicht einer Bitkette (Bitstring) wird oft in der Kryptographie und bei anderen Anwendungen benötigt. Der Hamming-Abstand zweier Wörter A und B kann als das Hamming-Gewicht von A xor B berechnet werden.
Das Problem, das Hamming-Gewicht effizient zu berechnen, wurde gründlich untersucht. Einige Prozessoren haben dafür einen einzelnen Befehl, und andere haben parallele Operationen auf Bitvektoren. Für Prozessoren, denen diese Eigenschaften fehlen, basieren die besten Lösungen auf dem Addieren von Abzählungen in einem Baummuster. Folgendes Beispiel zeigt die Berechnung der Anzahl der 1-bits in der 16-bit-Zahl a = 0110 1100 1011 1010. Dabei werden die Operatoren der Programmiersprache C verwendet: X >> Y bedeutet X um Y bit nach rechts zu verschieben, X & Y bedeutet das bitweise UND von X und Y, und + ist die gewöhnliche Addition:
| Ausdruck | Zwischenergebnis | Kommentar | ||
|---|---|---|---|---|
| in C-Syntax | Binär | Dezimal | ||
a |
01 10 11 00 10 11 10 10 | die ursprüngliche Zahl a | ||
b0 = (a >> 0) & 01 01 01 01 01 01 01 01 |
b0 = a & 0x5555; |
01 00 01 00 00 01 00 00 | 1,0,1,0,0,1,0,0 | jedes zweite Bit aus a |
b1 = (a >> 1) & 01 01 01 01 01 01 01 01 |
b1 = (a >> 1) & 0x5555; |
00 01 01 00 01 01 01 01 | 0,1,1,0,1,1,1,1 | die verbleibenden Bits aus a |
c = b0 + b1 |
c = b0 + b1; |
01 01 10 00 01 10 01 01 | 1,1,2,0,1,2,1,1 | Liste mit Anzahl der 1 in jedem 2-bit Segment aus a |
d0 = (c >> 0) & 0011 0011 0011 0011 |
d0 = c & 0x3333; |
0001 0000 0010 0001 | 1,0,2,1 | jede zweite Anzahl aus c |
d2 = (c >> 2) & 0011 0011 0011 0011 |
d2 = (c >> 2) & 0x3333; |
0001 0010 0001 0001 | 1,2,1,1 | die verbleibenden Anzahlen aus c |
e = d0 + d2 |
e = d0 + d2; |
0010 0010 0011 0010 | 2,2,3,2 | Liste mit Anzahl der 1 in jedem 4-bit Segment aus a |
f0 = (e >> 0) & 00001111 00001111 |
f0 = e & 0x0f0f; |
00000010 00000010 | 2,2 | jede zweite Anzahl aus e |
f4 = (e >> 4) & 00001111 00001111 |
f4 = (e >> 4) & 0x0f0f; |
00000010 00000011 | 2,3 | die verbleibenden Anzahlen aus e |
g = f0 + f4 |
g = f0 + f4; |
00000100 00000101 | 4,5 | Liste mit Anzahl der 1 in jedem 8-bit Segment aus a |
h0 = (g >> 0) & 0000000011111111 |
h0 = g & 0x00ff; |
0000000000000101 | 5 | jede zweite Anzahl aus g |
h8 = (g >> 8) & 0000000011111111 |
h8 = (g >> 8) & 0x00ff; |
0000000000000100 | 4 | die verbleibenden Anzahlen aus g |
i = h0 + h8 |
i = h0 + h8; |
0000000000001001 | 9 | Endergebnis; Zahl der 1-Bits in a |
Eine Alternative ist, so lange jeweils das niederwertigste 1-Bit aus einem Wert zu löschen, bis er Null ist. Wenn die verarbeiteten Werte meist ein niedriges Hamming-Gewicht haben, kann diese Methode, hier in der Sprache C dargestellt, effizienter sein:
#include <stdint.h>
int popcount (uint64_t x) {
int c = 0;
while (x) x &= x-1, ++c;
return c;
}
__builtin_popcount, die eine Prozessoranweisung, falls verfügbar, oder ansonsten eine effiziente Bibliotheksimplementierung verwendet. Der LLVM-GCC bietet diese Funktion ab der Version 1.5 im Juni 2005.bitset eine count() Methode, die die Anzahl der gesetzten Bits zählt. Seit C++20 gibt es die Template-Funktion std::popcount( T ), die für alle standard Integer-Typen explizit spezialisiert ist.BitSet eine BitSet.cardinality() Methode, die die Anzahl der gesetzten Bits zählt. Darüber hinaus gibt es die Funktionen Integer.bitCount(int) und Long.bitCount(long), um Bits in primitiven 32-Bit und 64-Bit-Integern zu zählen. Auch die BigInteger Klasse für große Genauigkeit hat eine BigInteger.bitCount()-Methode, die Bits zählt.popCount -Funktion, die auf allen Typen verfügbar ist, die Instanzen der Bits-Klasse sind (verfügbar aus dem Data.Bits-Modul).BIT_COUNT() als Standardfunktion.int.bit_count()SADD Instruktion. SADD a,b,c zählt alle Bits die 1 sind in b und 0 in c und schreibt das Ergebnis nach a.