Wie kann man die Anzahl der gesetzten Bits in einer 32-Bit-Ganzzahl zählen?

Question

8 Bits, die die Zahl 7 darstellen, sehen wie folgt aus:

00000111

Drei Bits sind gesetzt.

Wie lauten die Algorithmen zur Bestimmung der Anzahl der gesetzten Bits in einer 32-Bit-Ganzzahl?

Answer 1

Dies ist bekannt als die Hamming Gewicht ', 'popcount' oder 'sideways addition'.

Einige CPUs haben dafür einen einzigen eingebauten Befehl, andere haben parallele Befehle, die auf Bit-Vektoren wirken. Befehle wie der x86-Befehl popcnt (auf CPUs, wo es unterstützt wird) wird mit ziemlicher Sicherheit am schnellsten für eine einzelne ganze Zahl sein. Bei einigen anderen Architekturen kann ein langsamer Befehl mit einer mikrokodierten Schleife implementiert sein, die ein Bit pro Zyklus testet ( Zitate erforderlich - Hardware popcount ist normalerweise schnell, wenn es überhaupt existiert.).

Welcher Algorithmus am besten geeignet ist, hängt davon ab, welche CPU Sie verwenden und wie Ihr Nutzungsverhalten aussieht.

Ihr Compiler weiß vielleicht, wie man etwas macht, das für die spezifische CPU, für die Sie kompilieren, gut ist, z.B. C++20 std::popcount() oder C++ std::bitset<32>::count() als portabler Weg zum Zugriff auf eingebaute / intrinsische Funktionen (siehe eine weitere Antwort zu dieser Frage). Aber Ihr Compiler die Wahl der Fallback für Ziel-CPUs, die nicht über Hardware popcnt möglicherweise nicht optimal für Ihren Anwendungsfall. Oder Ihre Sprache (z. B. C) bietet möglicherweise keine portable Funktion, die einen CPU-spezifischen popcount verwenden könnte, wenn es einen gibt.

---

Portable Algorithmen, die keine HW-Unterstützung benötigen (oder davon profitieren)

Eine vorausgefüllte Tabellensuchmethode kann sehr schnell sein, wenn Ihre CPU einen großen Cache hat und Sie viele dieser Operationen in einer engen Schleife durchführen. Sie kann jedoch durch die Kosten eines "Cache-Misses" beeinträchtigt werden, bei dem die CPU einen Teil der Tabelle aus dem Hauptspeicher abrufen muss. (Schauen Sie jedes Byte separat nach, um die Tabelle klein zu halten.) Wenn Sie popcount für einen zusammenhängenden Bereich von Zahlen benötigen, ändert sich bei Gruppen von 256 Zahlen nur das untere Byte, was dies sehr gut macht .

Wenn Sie wissen, dass Ihre Bytes größtenteils 0 oder größtenteils 1 sein werden, gibt es effiziente Algorithmen für diese Szenarien, z. B. das Löschen der niedrigsten Menge mit einem Bithack in einer Schleife, bis sie Null wird.

Meiner Meinung nach ist der folgende Algorithmus, der als "paralleler" oder "SWAR-Algorithmus mit variabler Genauigkeit" bekannt ist, ein sehr guter Allzweckalgorithmus. Ich habe diesen Algorithmus in einer C-ähnlichen Pseudosprache ausgedrückt. Möglicherweise müssen Sie ihn für eine bestimmte Sprache anpassen (z. B. mit uint32_t für C++ und >>> in Java):

GCC10 und clang 10.0 können dieses Muster / Idiom erkennen und kompilieren es zu einer Hardware popcnt oder gleichwertige Anweisung, wenn verfügbar, so dass Sie das Beste aus beiden Welten. ( https://godbolt.org/z/qGdh1dvKK )

int numberOfSetBits(uint32_t i)
{
     // Java: use int, and use >>> instead of >>. Or use Integer.bitCount()
     // C or C++: use uint32_t
     i = i - ((i >> 1) & 0x55555555);        // add pairs of bits
     i = (i & 0x33333333) + ((i >> 2) & 0x33333333);  // quads
     i = (i + (i >> 4)) & 0x0F0F0F0F;        // groups of 8
     return (i * 0x01010101) >> 24;          // horizontal sum of bytes
}

Für JavaScript: zur Ganzzahl zwingen con |0 für die Leistung: ändern Sie die erste Zeile in i = (i|0) - ((i >> 1) & 0x55555555);

Dies ist der Algorithmus mit dem besten Worst-Case-Verhalten aller besprochenen Algorithmen, so dass er mit allen Nutzungsmustern und Werten, die Sie ihm vorgeben, effizient umgehen kann. (Seine Leistung ist auf normalen CPUs, auf denen alle Integer-Operationen einschließlich Multiplikation zeitkonstant sind, nicht datenabhängig. Bei "einfachen" Eingaben wird er nicht schneller, aber er ist immer noch ziemlich anständig).

Referenzen:

• https://graphics.stanford.edu/~seander/bithacks.html
• https://en.wikipedia.org/wiki/Hamming_weight
• http://gurmeet.net/puzzles/fast-bit-counting-routines/
• http://aggregate.ee.engr.uky.edu/MAGIC/#Population%20Count%20(Ones%20Count)

---

So funktioniert dieser SWAR-Bithacken:

i = i - ((i >> 1) & 0x55555555);

Der erste Schritt ist eine optimierte Version der Maskierung, um die ungeraden/geraden Bits zu isolieren, die Verschiebung, um sie aneinanderzureihen, und die Addition. Dies führt effektiv 16 separate Additionen in 2-Bit-Akkumulatoren durch ( SWAR = SIMD innerhalb eines Registers ). Wie (i & 0x55555555) + ((i>>1) & 0x55555555) .

Im nächsten Schritt werden die ungeraden/geraden acht dieser 16x 2-Bit-Akkumulatoren genommen und erneut addiert, was 8x 4-Bit-Summen ergibt. Die i - ... Eine Optimierung ist diesmal nicht möglich, so dass nur eine Maskierung vor/nach der Verschiebung erfolgt. Unter Verwendung der gleichen 0x33... beide Male konstant anstelle von 0xccc... vor dem Verschieben ist eine gute Sache, wenn man für ISAs kompiliert, die 32-Bit-Konstanten in Registern separat konstruieren müssen.

Der letzte Schritt des Verschiebens und Hinzufügens von (i + (i >> 4)) & 0x0F0F0F0F erweitert sich auf 4x 8-Bit-Akkumulatoren. Er maskiert nach Addieren statt vorher, denn der Höchstwert in einem 4-Bit-Akkumulator ist 4 , wenn alle 4 Bits der entsprechenden Eingangsbits gesetzt sind. 4+4 = 8, was immer noch in 4 Bits passt, so dass ein Übertrag zwischen Nibble-Elementen unmöglich ist in i + (i >> 4) .

Bislang handelt es sich dabei um ganz normale SIMD mit SWAR-Techniken und einigen cleveren Optimierungen. Wenn man das gleiche Muster für 2 weitere Schritte beibehält, kann man sich auf 2x 16-Bit und dann 1x 32-Bit erweitern. Aber es gibt einen effizienteren Weg auf Maschinen mit schneller Hardware-Multiplikation:

Sobald wir nur noch wenige "Elemente" haben, eine Multiplikation mit einer magischen Konstante kann alle Elemente zum obersten Element summieren . In diesem Fall sind es Byte-Elemente. Die Multiplikation erfolgt durch Linksverschiebung und Addition, also *ein Vielfaches von `x 0x01010101führt zux + (x<<8) + (x<<16) + (x<<24)` .** Unsere 8-Bit-Elemente sind breit genug (und haben eine so geringe Anzahl), dass dies nicht zu Übertragungen führt. in die oberen 8 Bits.

Eine 64-Bit-Version dieser kann 8x 8-Bit-Elemente in eine 64-Bit-Ganzzahl mit einem 0x0101010101010101-Multiplikator einfügen und das High-Byte mit >>56 . Es sind also keine zusätzlichen Schritte nötig, nur breitere Konstanten. Dies ist, was GCC verwendet für __builtin_popcountll auf x86-Systemen, wenn die Hardware popcnt Anweisung ist nicht aktiviert. Wenn Sie hierfür Builtins oder Intrinsics verwenden können, sollten Sie dies tun, um dem Compiler die Möglichkeit zu geben, zielspezifische Optimierungen vorzunehmen.

---

Mit vollem SIMD für breitere Vektoren (z.B. Zählen eines ganzen Arrays)

Dieser bitweise SWAR-Algorithmus könnte parallelisiert werden, so dass er in mehreren Vektorelementen gleichzeitig ausgeführt wird, anstatt in einem einzigen Integer-Register, um eine Beschleunigung auf CPUs mit SIMD, aber ohne verwendbaren Popcount-Befehl zu erreichen. (z.B. x86-64 Code, der auf jeder CPU laufen muss, nicht nur Nehalem oder später).

Der beste Weg, Vektorbefehle für popcount zu verwenden, ist jedoch normalerweise die Verwendung einer Variablen-Mischung, um eine Tabellensuche für jeweils 4 Bits eines jeden Bytes parallel durchzuführen. (Die 4 Bits indizieren eine Tabelle mit 16 Einträgen, die in einem Vektorregister gespeichert ist).

Auf Intel-CPUs kann der Hardware-64-Bit-Popcnt-Befehl die Leistung eines SSSE3 PSHUFB bit-parallele Implementierung um etwa einen Faktor 2, aber nur wenn Ihr Compiler das richtig hinbekommt . Andernfalls kann SSE einen deutlichen Vorsprung erzielen. Neuere Compiler-Versionen sind sich der popcnt false dependency Problem bei Intel .

• https://github.com/WojciechMula/sse-popcount modernste x86 SIMD Popcount für SSSE3, AVX2, AVX512BW, AVX512VBMI oder AVX512 VPOPCNT. Verwendung von Harley-Seal über Vektoren hinweg, um den Popcount innerhalb eines Elements aufzuschieben. (Auch ARM NEON)
• Zählen von 1 Bit (Populationszählung) bei großen Daten mit AVX-512 oder AVX-2
• verwandt: https://github.com/mklarqvist/positional-popcount - getrennte Zählungen für jede Bit-Position mehrerer 8-, 16-, 32- oder 64-Bit-Ganzzahlen. (Auch hier gilt, dass x86 SIMD, einschließlich AVX-512, das dies sehr gut kann, mit vpternlogd Herstellung von Harley-Seal sehr gut.)

Answer 2

Einige Sprachen machen die Operation auf eine Weise portabel, die kann Effiziente Hardwareunterstützung, falls vorhanden, ansonsten eine hoffentlich brauchbare Bibliothek als Fallback verwenden.

Zum Beispiel (aus eine Tabelle nach Sprachen ):

• C++ hat std::bitset<>::count() , oder C++20 std::popcount(T x)
• Java hat java.lang.Integer.bitCount() (auch für Long oder BigInteger)
• C# hat System.Numerics.BitOperations.PopCount()
• Python hat int.bit_count() (seit 3.10)

Allerdings gelingt es nicht allen Compilern/Bibliotheken, die HW-Unterstützung zu nutzen, wenn sie verfügbar ist. (Vor allem MSVC, auch mit Optionen, die std::popcount inline als x86 popcnt machen, seine std::bitset::count immer noch eine Nachschlagetabelle verwendet. Das wird sich hoffentlich in zukünftigen Versionen ändern.)

Berücksichtigen Sie auch die eingebauten Funktionen Ihres Compilers, wenn die portable Sprache nicht über diese grundlegende Bit-Operation verfügt. In GNU C zum Beispiel:

int __builtin_popcount (unsigned int x);
int __builtin_popcountll (unsigned long long x);

Im schlimmsten Fall (keine Single-Instruction-HW-Unterstützung) generiert der Compiler einen Aufruf einer Funktion (die im aktuellen GCC einen Shift- und Bit-Hack verwendet). wie diese Antwort (zumindest für x86). Im besten Fall gibt der Compiler einen CPU-Befehl aus, um die Aufgabe zu erledigen. (Genau wie eine * o / Operator - GCC wird eine Hardware-Multiplikations- oder Divisionsanweisung verwenden, falls verfügbar, andernfalls wird eine libgcc-Hilfsfunktion aufgerufen). Oder noch besser, wenn der Operand nach dem Inlining eine Kompilierzeit-Konstante ist, kann er eine Konstanten-Propagation durchführen, um ein Kompilierzeit-konstantes Popcount-Ergebnis zu erhalten.

Die GCC-Builtins funktionieren sogar plattformübergreifend. Popcount ist in der x86-Architektur fast zum Mainstream geworden, so dass es sinnvoll ist, das Builtin jetzt zu verwenden, damit man es neu kompilieren kann, um eine Hardware-Anweisung zu inlinen, wenn man mit -mpopcnt oder etwas, das dies beinhaltet (z. B. https://godbolt.org/z/Ma5e5a ). Bei anderen Architekturen gibt es Popcount schon seit Jahren, aber in der x86-Welt sind immer noch einige alte Core 2 und ähnliche alte AMD-CPUs im Einsatz.

---

Auf x86 können Sie dem Compiler mitteilen, dass er die Unterstützung für popcnt Unterricht mit -mpopcnt (auch impliziert durch -msse4.2 ). Siehe GCC x86-Optionen . -march=nehalem -mtune=skylake (oder -march= was auch immer für eine CPU Sie für Ihren Code annehmen und darauf abstimmen wollen) könnte eine gute Wahl sein. Die Ausführung der resultierenden Binärdatei auf einer älteren CPU führt zu einem illegalen Befehlsfehler.

Um Binärdateien zu erstellen, die für den Rechner optimiert sind, auf dem Sie sie erstellen, verwenden. -march=native (mit gcc, clang, oder ICC).

MSVC bietet ein Intrinsic für den x86 popcnt Anleitung aber im Gegensatz zu gcc ist es wirklich ein Intrinsic für den Hardware-Befehl und erfordert Hardware-Unterstützung.

---

Verwendung von std::bitset<>::count() anstelle eines eingebauten

Theoretisch sollte jeder Compiler, der weiß, wie man Popcount für die Ziel-CPU effizient einsetzt, diese Funktionalität über ISO C++ zur Verfügung stellen std::bitset<> . In der Praxis sind Sie mit dem Bit-Hack AND/shift/ADD in einigen Fällen bei einigen Ziel-CPUs besser dran.

Für Zielarchitekturen, bei denen Hardware-Popcount eine optionale Erweiterung ist (wie x86), haben nicht alle Compiler eine std::bitset die es nutzt, wenn es verfügbar ist. MSVC hat zum Beispiel keine Möglichkeit, die popcnt Unterstützung zur Kompilierzeit, und es ist std::bitset<>::count verwendet immer eine Tabellensuche auch bei /Ox /arch:AVX (was SSE4.2 voraussetzt, was wiederum die popcnt-Funktion impliziert.) (Update: siehe unten; das tut C++20 von MSVC erhalten std::popcount x86 zu verwenden popcnt aber immer noch nicht sein bitset<>::count. MSVC könnte das beheben, indem sie ihre Standardbibliotheksheader aktualisieren, um std::popcount zu verwenden, wenn es verfügbar ist).

Aber zumindest erhält man etwas Portables, das überall funktioniert, und mit gcc/clang und den richtigen Target-Optionen erhält man Hardware-Popcount für Architekturen, die es unterstützen.

#include <bitset>
#include <limits>
#include <type_traits>

template<typename T>
//static inline  // static if you want to compile with -mpopcnt in one compilation unit but not others
typename std::enable_if<std::is_integral<T>::value,  unsigned >::type 
popcount(T x)
{
    static_assert(std::numeric_limits<T>::radix == 2, "non-binary type");

    // sizeof(x)*CHAR_BIT
    constexpr int bitwidth = std::numeric_limits<T>::digits + std::numeric_limits<T>::is_signed;
    // std::bitset constructor was only unsigned long before C++11.  Beware if porting to C++03
    static_assert(bitwidth <= std::numeric_limits<unsigned long long>::digits, "arg too wide for std::bitset() constructor");

    typedef typename std::make_unsigned<T>::type UT;        // probably not needed, bitset width chops after sign-extension

    std::bitset<bitwidth> bs( static_cast<UT>(x) );
    return bs.count();
}

Siehe asm von gcc, clang, icc und MSVC auf dem Godbolt-Compiler-Explorer.

x86-64 gcc -O3 -std=gnu++11 -mpopcnt sendet dies aus:

unsigned test_short(short a) { return popcount(a); }
    movzx   eax, di      # note zero-extension, not sign-extension
    popcnt  rax, rax
    ret

unsigned test_int(int a) { return popcount(a); }
    mov     eax, edi
    popcnt  rax, rax        # unnecessary 64-bit operand size
    ret

unsigned test_u64(unsigned long long a) { return popcount(a); }
    xor     eax, eax     # gcc avoids false dependencies for Intel CPUs
    popcnt  rax, rdi
    ret

PowerPC64 gcc -O3 -std=gnu++11 emittiert (für die int arg-Version):

    rldicl 3,3,0,32     # zero-extend from 32 to 64-bit
    popcntd 3,3         # popcount
    blr

Dieser Quelltext ist überhaupt nicht x86- oder GNU-spezifisch, sondern lässt sich nur mit gcc/clang/icc gut kompilieren, zumindest wenn es um x86 (einschließlich x86-64) geht.

Beachten Sie auch, dass gcc's Fallback für Architekturen ohne single-instruction popcount ein byte-at-a-time table lookup ist. Das ist nicht wunderbar für ARM, zum Beispiel .

C++20 hat std::popcount(T)

Aktuelle libstdc++-Header definieren es leider mit einem Sonderfall if(x==0) return 0; am Anfang, was Clang beim Kompilieren für x86 nicht wegoptimiert:

#include <bit>
int bar(unsigned x) {
    return std::popcount(x);
}

clang 11.0.1 -O3 -std=gnu++20 -march=nehalem ( https://godbolt.org/z/arMe5a )

# clang 11
    bar(unsigned int):                                # @bar(unsigned int)
        popcnt  eax, edi
        cmove   eax, edi         # redundant: if popcnt result is 0, return the original 0 instead of the popcnt-generated 0...
        ret

Aber GCC kompiliert gut:

# gcc 10
        xor     eax, eax         # break false dependency on Intel SnB-family before Ice Lake.
        popcnt  eax, edi
        ret

Sogar MSVC kommt gut damit zurecht, solange man die -arch:AVX oder später (und aktivieren Sie C++20 mit -std:c++latest ). https://godbolt.org/z/7K4Gef

int bar(unsigned int) PROC                                 ; bar, COMDAT
        popcnt  eax, ecx
        ret     0
int bar(unsigned int) ENDP                                 ; bar

Answer 3

Meiner Meinung nach ist die "beste" Lösung diejenige, die von einem anderen Programmierer (oder dem ursprünglichen Programmierer zwei Jahre später) ohne umfangreiche Kommentare gelesen werden kann. Sie wollen vielleicht die schnellste oder cleverste Lösung, die einige bereits geliefert haben, aber ich ziehe die Lesbarkeit jederzeit der Cleverness vor.

unsigned int bitCount (unsigned int value) {
    unsigned int count = 0;
    while (value > 0) {           // until all bits are zero
        if ((value & 1) == 1)     // check lower bit
            count++;
        value >>= 1;              // shift bits, removing lower bit
    }
    return count;
}

Wenn Sie mehr Geschwindigkeit wünschen (und vorausgesetzt, Sie dokumentieren es gut, um Ihren Nachfolgern zu helfen), können Sie eine Tabellensuche verwenden:

// Lookup table for fast calculation of bits set in 8-bit unsigned char.

static unsigned char oneBitsInUChar[] = {
//  0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F (<- n)
//  =====================================================
    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, // 0n
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, // 1n
    : : :
    4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, // Fn
};

// Function for fast calculation of bits set in 16-bit unsigned short.

unsigned char oneBitsInUShort (unsigned short x) {
    return oneBitsInUChar [x >>    8]
         + oneBitsInUChar [x &  0xff];
}

// Function for fast calculation of bits set in 32-bit unsigned int.

unsigned char oneBitsInUInt (unsigned int x) {
    return oneBitsInUShort (x >>     16)
         + oneBitsInUShort (x &  0xffff);
}

Diese sind auf bestimmte Datentypgrößen angewiesen und daher nicht sehr portabel. Aber da viele Leistungsoptimierungen ohnehin nicht portabel sind, ist das vielleicht kein Problem. Wenn Sie Portabilität wünschen, würde ich mich an die lesbare Lösung halten.

Answer 4

Aus Hacker's Delight, S. 66, Abbildung 5-2

int pop(unsigned x)
{
    x = x - ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F;
    x = x + (x >> 8);
    x = x + (x >> 16);
    return x & 0x0000003F;
}

Wird in ca. 20 Anweisungen ausgeführt (arch-abhängig), keine Verzweigung.

Hackerfreuden est Herrlich! Äußerst empfehlenswert.

Answer 5

Ich denke, der schnellste Weg - ohne Verwendung von Nachschlagetabellen und Popcount -ist das Folgende. Sie zählt die gesetzten Bits mit nur 12 Operationen.

int popcount(int v) {
    v = v - ((v >> 1) & 0x55555555);                // put count of each 2 bits into those 2 bits
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // put count of each 4 bits into those 4 bits  
    return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}

Es funktioniert, weil man die Gesamtzahl der gesetzten Bits zählen kann, indem man sie in zwei Hälften teilt, die Anzahl der gesetzten Bits in beiden Hälften zählt und sie dann addiert. Auch bekannt als Divide and Conquer Paradigma. Lassen Sie uns ins Detail gehen

v = v - ((v >> 1) & 0x55555555); 

Die Anzahl der Bits in zwei Bits kann sein 0b00 , 0b01 o 0b10 . Lassen Sie uns versuchen, dies auf 2 Bits auszuarbeiten.

 ---------------------------------------------
 |   v    |   (v >> 1) & 0b0101   |  v - x   |
 ---------------------------------------------
   0b00           0b00               0b00   
   0b01           0b00               0b01     
   0b10           0b01               0b01
   0b11           0b01               0b10

Die letzte Spalte zeigt die Anzahl der gesetzten Bits in jedem Zwei-Bit-Paar. Wenn die Zwei-Bit-Zahl >= 2 (0b10) dann and produziert 0b01 sonst erzeugt es 0b00 .

v = (v & 0x33333333) + ((v >> 2) & 0x33333333); 

Diese Aussage sollte leicht zu verstehen sein. Nach der ersten Operation haben wir die Anzahl der gesetzten Bits in allen zwei Bits, jetzt summieren wir diese Anzahl in allen 4 Bits.

v & 0b00110011         //masks out even two bits
(v >> 2) & 0b00110011  // masks out odd two bits

Wir addieren dann das obige Ergebnis und erhalten die Gesamtzahl der gesetzten Bits in 4 Bits. Die letzte Aussage ist die kniffligste.

c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;

Lassen Sie uns das weiter aufschlüsseln...

v + (v >> 4)

Es ist ähnlich wie bei der zweiten Anweisung, nur dass wir die gesetzten Bits in 4er-Gruppen zählen. Wir wissen - aufgrund unserer vorherigen Operationen - dass jedes Nibble die Anzahl der gesetzten Bits enthält. Schauen wir uns ein Beispiel an. Nehmen wir an, wir haben das Byte 0b01000010 . Das bedeutet, dass das erste Nibble mit 4 Bits und das zweite mit 2 Bits belegt ist. Jetzt addieren wir diese Nibbles zusammen.

v = 0b01000010
(v >> 4) = 0b00000100
v + (v >> 4) = 0b01000010 + 0b00000100

Sie gibt die Anzahl der gesetzten Bits in einem Byte an, im zweiten Nibble 0b01000110 und deshalb maskieren wir die ersten vier Bytes aller Bytes der Nummer (und verwerfen sie).

0b01000110 & 0x0F = 0b00000110

Jedes Byte enthält nun die Anzahl der gesetzten Bits. Wir müssen sie alle zusammenzählen. Der Trick ist, das Ergebnis zu multiplizieren mit 0b10101010 die eine interessante Eigenschaft hat. Wenn unsere Zahl vier Bytes hat, A B C D wird eine neue Nummer mit diesen Bytes erzeugt A+B+C+D B+C+D C+D D . Für eine 4-Byte-Zahl können maximal 32 Bits gesetzt werden, die wie folgt dargestellt werden können 0b00100000 .

Alles, was wir jetzt brauchen, ist das erste Byte, das die Summe aller gesetzten Bits in allen Bytes enthält, und das erhalten wir durch >> 24 . Dieser Algorithmus wurde entwickelt für 32 bit Worte, kann aber leicht geändert werden für 64 bit Worte.