Hamming-Gewicht
# Hamming-Gewicht

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.

## Geschichte

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.

## Anwendungsbeispiele

Das Hamming-Gewicht wird unter anderem in der Informationstheorie, der Kodierungstheorie und der Kryptographie verwendet. Beispiele für Anwendungen des Hamming-Gewichts sind:

* Bei der binären Modulo-Exponentiation ist die Anzahl der modularen Multiplikationen, die für einen Exponenten e erforderlich sind, log2 e + Gewicht(e). Dies ist der Grund dafür, dass für den öffentlichen Schlüsselwert e, der in RSA verwendet wird, typischerweise eine Zahl mit niedrigem Hamming-Gewicht gewählt wird.
* Das Hamming-Gewicht bestimmt die Pfadlängen zwischen den Knoten in Chords verteilten Hash-Tabellen.
* Die Suche in biometrischen Datenbanken zur Iris-Erkennung wird typischerweise so implementiert, dass der Hamming-Abstand zu jedem gespeicherten Datensatz berechnet wird.
* Bei Computerschach-Programmen, die eine Bitboard-Darstellung verwenden, gibt das Hamming-Gewicht eines Bitboards die Anzahl der Figuren eines gegebenen Typs, die im Spiel verbleiben, oder die Anzahl der Quadrate des Bretts, die von den Figuren eines Spielers gesteuert werden, wieder und stellt einen wichtigen Faktor bei der Berechnung des Werts einer Position dar.
* Das Hamming-Gewicht kann verwendet werden, um mittels der Identität ffs(x) = pop(x ^ (~ (-x))) in effizienter Art und Weise das erste gesetzte Bit zu finden (find first set). Dies ist auf Plattformen wie SPARC nützlich, die Hardware-Instruktionen für das Hamming-Gewicht aufweisen, aber keine Hardware-Instruktionen um das erste gesetzte Bit zu finden.
* Die Berechnung des Hamming-Gewichts kann als die Umrechnung vom Unärsystem zu binären Zahlen interpretiert werden.

## Effiziente Implementierung

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, wie man die Berechnung des Hamming-Gewichts effizient implementieren kann, wurde gründlich untersucht. Einige Prozessoren haben einen einzelnen Befehl, um es zu berechnen 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. Um zum Beispiel die Anzahl der 1er bits in dieser 16-bitting binären Zahl a = 0110 1100 1011 1010 zu berechnen, können die folgenden Berechnungen durchgeführt werden:

| Ausdruck | Binär | Dezimal | Kommentar |
| - | - | - | - |
| 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 | 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 | 00 01 01 00 01 01 01 01 | 0,1,1,0,1,1,1,1 | die verbleibenden Bits aus a |
| 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 | 0001 0000 0010 0001 | 1,0,2,1 | jede zweite Anzahl aus c |
| d2 = (c >> 2) & 0011 0011 0011 0011 | 0001 0010 0001 0001 | 1,2,1,1 | die verbleibenden Anzahlen aus c |
| 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 | 00000010 00000010 | 2,2 | jede zweite Anzahl aus e |
| f4 = (e >> 4) & 00001111 00001111 | 00000010 00000011 | 2,3 | die verbleibenden Anzahlen aus e |
| g = f0 + f4 | 00000100 00000101 | 4,5 | Liste mit Anzahl der 1 in jedem 8-bit Segment aus a |
| h0 = (g >> 0) & 0000000011111111 | 0000000000000101 | 5 | jede zweite Anzahl aus g |
| h8 = (g >> 8) & 0000000011111111 | 0000000000000100 | 4 | die verbleibenden Anzahlen aus g |
| i = h0 + h8 | 0000000000001001 | 9 | das Ergebnis für das 16-bit Wort |

Hier wurden die Operationen wie in der C-Programmiersprache verwendet, X >> Y bedeutet also X um Y bit nach rechts zu verschieben, X & Y bedeutet das bitweise UND von X und Y und + ist die gewöhnliche Addition.

## Pseudocode

Die folgende Pseudocode zeigt eine Funktion zur Berechnung des Hamming-Gewichts der eingegebenen Zeichenkette. In der while-Schleife werden schrittweise alle Bits der Zeichenkette rechts nach links durchlaufen und geprüft, ob sie gesetzt sind.

## Sprachunterstützung

* Einige C-Compiler bieten intrinsische Funktionen, die Bit-Zählfunktionen anbieten. Zum Beispiel enthält der GCC (ab Version 3.4 im April 2004) eine eingebaute Funktion __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.
* In der C++ Standard Template Library (C++ STL) hat die Bit-Array-Datenstruktur bitset eine count Methode, die die Anzahl der gesetzten Bits zählt. Seit C++20 gibt es die Tempalte-Funktion std::popcount( T ), die für alle standard Integer-Typen explizit spezialisiert ist.
* In Java hat die Bit-Array Datenstruktur 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.
* In Common Lisp gibt die Funktion logcount bei einer nicht-negativen Ganzzahl die Anzahl der 1 Bits zurück, für negative Ganzzahlen gibt sie die Anzahl der 0 Bits in der 2er-Komplement-Notation zurück. In beiden Fällen kann die Ganzzahl ein BIGNUM sein.
* Beginnend mit GHC 7.4 hat das Haskell-Basispaket eine popCount -Funktion, die auf allen Typen verfügbar ist, die Instanzen der Bits-Klasse sind (verfügbar aus dem Data.Bits-Modul).
* Die MySQL-Version der SQL-Sprache bietet BIT_COUNT als Standardfunktion.
* Ab Version 3.10 bietet Python die Methode int.bit_count

## Prozessorunterstützung

* Cray Supercomputer boten frühzeitig eine popcount-Maschineninstruktion an und es gibt Gerüchte, dass diese speziell von der National Security Agency der US-amerikanischen Regierung für Anwendungen zur Kryptoanalyse angefordert wurde.
* Einige der Maschinen der Control Data Corporation CYBER 70/170 Serie enthielten eine popcount Instruktion; in COMPASS wurde diese Instruktion als CXi kodiert.
* AMDs Barcelona-Architektur führte den abm (advanced bit manipulation) Befehlssatz ein und brachte die POPCNT Instruktion als Teil der SSE4a Erweiterung mit.
* Intel Core-Prozessoren führten eine POPCNT Instruktion mit der SSE4.2-Befehlssatzerweiterung ein, die zuerst in dem im November 2008 veröffentlichten Nehalem-basierten Core i7-Prozessor verfügbar war.
* Compaqs Alpha 21264A, veröffentlicht im Jahr 1999, war das erste CPU-Design der Alpha-Serie, das die Zähl-Erweiterung (CIX) hatte.
* Donald E. Knuths Modellcomputer MMIX, der MIX in seinem Buch The Art of Computer Programming ersetzen wird, hat eine 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.
* Die ARM-Architecture führte die VCNT-Instruktion als Teil der Advanced SIMD (NEON) Erweiterung ein.
