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[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, 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:

AusdruckBinärDezimalKommentar
a01 10 11 00 10 11 10 10die ursprüngliche Zahl a
b0 = (a >> 0) & 01 01 01 01 01 01 01 0101 00 01 00 00 01 00 001,0,1,0,0,1,0,0jedes zweite Bit aus a
b1 = (a >> 1) & 01 01 01 01 01 01 01 0100 01 01 00 01 01 01 010,1,1,0,1,1,1,1die verbleibenden Bits aus a
c = b0 + b101 01 10 00 01 10 01 011,1,2,0,1,2,1,1Liste mit Anzahl der 1 in jedem 2-bit Segment aus a
d0 = (c >> 0) & 0011 0011 0011 00110001 0000 0010 00011,0,2,1jede zweite Anzahl aus c
d2 = (c >> 2) & 0011 0011 0011 00110001 0010 0001 00011,2,1,1die verbleibenden Anzahlen aus c
e = d0 + d20010 0010 0011 00102,2,3,2Liste mit Anzahl der 1 in jedem 4-bit Segment aus a
f0 = (e >> 0) & 00001111 0000111100000010 000000102,2jede zweite Anzahl aus e
f4 = (e >> 4) & 00001111 0000111100000010 000000112,3die verbleibenden Anzahlen aus e
g = f0 + f400000100 000001014,5Liste mit Anzahl der 1 in jedem 8-bit Segment aus a
h0 = (g >> 0) & 000000001111111100000000000001015jede zweite Anzahl aus g
h8 = (g >> 8) & 000000001111111100000000000001004die verbleibenden Anzahlen aus g
i = h0 + h800000000000010019das 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.

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