Hamming-Gewicht

Hier fehlt eine Grafik, die leider im Moment aus technischen Gründen nicht angezeigt werden kann. Wir arbeiten daran!
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[1] 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.[2] 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.[3] Und Irving S. Reed führte 1954 ein Konzept ein, das dem Hamming-Gewicht für binäre Zahlen ähnlich ist.[4]

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.[5]
  • 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.[6]
  • Die Berechnung des Hamming-Gewichts kann als die Umrechnung vom Unärsystem zu binären Zahlen interpretiert werden.[7]

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, 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;
}

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.[8] Der LLVM-GCC bietet diese Funktion ab der Version 1.5 im Juni 2005.[9]
  • 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).[10]
  • Die MySQL-Version der SQL-Sprache bietet BIT_COUNT() als Standardfunktion.[11]
  • Ab Version 3.10 bietet Python die Methode int.bit_count()[12]

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.

Einzelnachweise

  1. ↑ Donald E. Knuth: Bitwise tricks & techniques; Binary Decision Diagrams. In: The Art of Computer Programming. Band 4, Fascicle 1. Addison–Wesley Professional, 2009, ISBN 0-321-58050-8 (Entwurf [PostScript; 1,2 MB; abgerufen am 23. Februar 2017]).
  2. ↑ Thomas M. Thompson: From Error-Correcting Codes through Sphere Packings to Simple Groups. In: The Carus Mathematical Monographs. Nr. 21. The Mathematical Association of America, 1983, S. 33.
  3. ↑ James Whitbread Lee Glaisher: On the residue of a binomial-theorem coefficient with respect to a prime modulus. In: The Quarterly Journal of Pure and Applied Mathematics. Nr. 30, 1899, S. 150–156 (gdz.sub.uni-goettingen.de [abgerufen am 23. Februar 2017]).
  4. ↑ Irving S. Reed: A Class of Multiple-Error-Correcting Codes and the Decoding Scheme. In: I.R.E. (I.E.E.E.). PGIT, Nr. 4, 1954, S. 38.
  5. ↑ Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, and Hari Balakrishnan: Chord. A scalable peer-to-peer lookup service for internet applications. In: Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications. ACM, New York 2001, S. 149–160, doi:10.1145/383059.383071.
  6. ↑ SPARC International, Inc. (Hrsg.): The SPARC architecture manual. Prentice Hall, Englewood Cliffs, N.J. 1992, ISBN 0-13-825001-4, S. 231 (gaisler.com [PDF] Version 8).
  7. ↑ David Blaxell: Computer Science and Statistics: Tenth Annual Symposium on the Interface. In: David Hogben, Dennis W. Fife (Hrsg.): NBS Special Publication. Nr. 503. U.S. Department of Commerce / National Bureau of Standards, Februar 1978, S. 146–156 (google.books.com).
  8. ↑ GCC 3.4 Release Notes GNU Project.
  9. ↑ LLVM 1.5 Release Notes LLVM Project.
  10. ↑ GHC 7.4.1 release notes.
  11. ↑ 12.11. Bit Functions – MySQL 5.0 Reference Manual.
  12. ↑ What’s New In Python 3.10 — Python 3.10.6 documentation. Abgerufen am 14. August 2022.