Ein Wert hat gerade Parität, wenn er eine gerade Anzahl von 1 Bits hat. Ein Wert hat eine ungerade Parität, wenn er eine ungerade Anzahl von 1 Bits hat. Zum Beispiel hat 0110 gerade Parität und 1110 hat ungerade Parität.
Ich muss 1 zurückgeben, wenn x gerade Parität hat.
Angenommen, Sie wissen, dass es sich um 32 Bits handelt.
Mal sehen, wie das funktioniert. Um es einfach zu halten, verwenden wir eine 8-Bit-Ganzzahl, für die wir die ersten beiden Shift / XORs überspringen können. Beschriften wir die Bits a bis h . Wenn wir unsere Nummer betrachten, sehen wir:
( a d d f ich h )
Die erste Operation ist x ^= x >> 4 (denken Sie daran, dass wir die ersten beiden Operationen überspringen, da wir in diesem Beispiel nur eine 8-Bit-Ganzzahl behandeln). Lassen Sie uns die neuen Werte jedes Bits schreiben, indem Sie die Buchstaben kombinieren, die XOR-verknüpft sind (zum Beispiel bedeutet ab , dass das Bit den Wert a x b
( a d d f ich> g h ) xor (0 <0 <0 <0> 0 <0> b c d )
Das Ergebnis sind die folgenden Bits:
( a b d b ich dh )
Die nächste Operation ist x ^= x >> 2 :
( a b d b ich> cg dh ) xor (0 0 a b d d >)
Das Ergebnis sind die folgenden Bits:
( a b ac bd ace bdf aceg bdfh )
Beachten Sie, wie wir beginnen, alle Bits auf der rechten Seite zu akkumulieren.
Die nächste Operation ist x ^= x >> 1 :
( a b ac bd ace bdf aceg bdfh ) xor (0 b ac bd ace bdf aceg )
Das Ergebnis sind die folgenden Bits:
( a ab abc abcd abcde abcdef abcdefgh abcdefgh )
Wir haben alle Bits im ursprünglichen Wort, XOR'd zusammen, im niedrigstwertigen Bit angesammelt. Dieses Bit ist jetzt genau dann null, wenn eine gerade Zahl von 1 Bits im Eingangswort vorhanden war (gerade Parität). Der gleiche Prozess funktioniert mit 32-Bit-Ganzzahlen (erfordert aber diese zwei zusätzlichen Verschiebungen, die wir in dieser Demonstration übersprungen haben).
Die letzte Zeile des Codes entfernt einfach alles außer dem niedrigstwertigen Bit ( & 1 ) und dreht es dann um ( ~x ). Das Ergebnis ist dann 1, wenn die Parität des Eingabewortes gerade war, oder sonst Null.
Die folgende Antwort wurde unverhohlen direkt aus Bit Twiddling Hacks von Sean Eron Anderson, [email protected] <übernommen / a>
Parität des Wortes mit einer Multiplikation berechnen
%Vor%Die folgende Methode berechnet die Parität des 32-Bit-Wertes in nur 8 Operationen & gt; mit einer Multiplikation.
%Vor%Auch für 64-Bit sind 8 Operationen immer noch genug.
Andrew Shapira hat sich das ausgedacht und es mir am 2. September 2007 geschickt.
Die Hauptidee ist dies. Setzen Sie das rechte "1" -Bit mit x & ( x - 1 ) außer Kraft. Sagen wir x = 13 (1101) und die Operation von x & ( x - 1 ) ist 1101 & 1100 , was 1100 ist. Beachten Sie, dass das am weitesten rechts gesetzte Bit in 0 konvertiert wird.
Jetzt x ist 1100 . Die Operation von x & ( x - 1 ) ist 1100 & 1011 ist 1000 . Beachten Sie, dass das ursprüngliche x 1101 ist und dass nach zwei Operationen von x & (x - 1) das x 1000 ist, d. H. Zwei gesetzte Bits werden nach zwei Operationen entfernt. Wenn nach odd Anzahl von Operationen, wird x zu Null, dann ist es eine ungerade Parität, sonst ist es eine gerade Parität.
Verallgemeinern @ TypelA die Antwort für jede Architektur:
%Vor%Auf GCC gibt es dafür eine eingebaute Funktion :
Eingebaute Funktion:
int __builtin_parity (unsigned int x)Gibt die Parität von
xzurück, d. h. die Anzahl der 1-Bits in x modulo 2.
i.e. Diese Funktion verhält sich wie has_odd_parity . Kehren Sie den Wert für has_even_parity um.
Dies ist garantiert die schnellste Alternative auf GCC. Natürlich ist seine Verwendung als solche nicht portierbar, aber Sie können es in Ihrer Implementierung verwenden, zum Beispiel durch ein Makro geschützt.
Das ist eine ziemlich alte Frage, aber ich poste das für jeden, der es in Zukunft benutzen könnte.
Ich werde kein Beispiel hinzufügen, das in c gemacht wird, da es bereits genügend gute Antworten gibt.
Falls das Endergebnis ein Stück Code sein soll, der mit einem c-Programm arbeiten (kompiliert werden kann), schlage ich Folgendes vor:
%Vor%Dies ist ein Stück Code, den ich verwende, um die Parität der berechneten Ergebnisse in einem 64-Bit-c-Programm zu prüfen, das mit MSVC kompiliert wurde. Sie können es natürlich auf 32-Bit oder andere Compiler portieren.
Dies hat den Vorteil, dass es viel schneller ist als die Verwendung von c und es nutzt auch die CPU-Funktionalität.
In diesem Beispiel wird ein Parameter als Parameter übergeben (in RCX übergeben - __fastcall Aufrufkonvention). Es erhöht es um 0 und setzt damit den cpus Parity Flag und setzt dann eine Variable (RAX) auf 0 oder 1 wenn Parity Flag an ist oder nicht.