Wie kann ich überprüfen, ob ein Wert eine gerade Parität von Bits oder eine ungerade hat?

Ein Wert hat gerade Parität wenn es 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, 0110 hat gerade Parität, und 1110 hat eine ungerade Parität.

Ich muss zurück 1 wenn x hat gerade Parität.

int has_even_parity(unsigned int x) {
    return
}

x ^= x >> 16;
x ^= x >> 8;
x ^= x >> 4;
x ^= x >> 2;
x ^= x >> 1;
return (~x) & 1;

Angenommen, Sie wissen, dass Ints 32 Bit sind.

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. Lassen Sie uns die Bits beschriften a durch h. Wenn wir auf unsere Nummer schauen, sehen wir:

( a b c d e f g h )

Die erste Operation ist x ^= x >> 4 (Denken Sie daran, dass wir die ersten beiden Operationen überspringen, da wir es in diesem Beispiel nur mit einer 8-Bit-Ganzzahl zu tun haben). Lassen Sie uns die neuen Werte jedes Bits schreiben, indem wir die XOR-verknüpften Buchstaben kombinieren (z. B. ab bedeutet, dass das Bit den Wert hat a xoder b).

( a b c d e f g h ) oder ( 0 0 0 0 a b c d )

Das Ergebnis sind die folgenden Bits:

( a b c d ä bf CG dh )

Die nächste Operation ist x ^= x >> 2:

( a b c d ä bf CG dh ) xoder ( 0 0 a b c d ä bf )

Das Ergebnis sind die folgenden Bits:

( a b ac bd As bdf aceg bdfh )

Beachten Sie, wie wir beginnen, alle Bits auf der rechten Seite anzusammeln.

Die nächste Operation ist x ^= x >> 1:

( a b ac bd As bdf aceg bdfh ) xoder ( 0 a b ac bd As bdf aceg )

Das Ergebnis sind die folgenden Bits:

( a ab ABC A B C D abcde abcdef abcdefg A B C D E F G H )

Wir haben alle Bits im ursprünglichen Wort, zusammen XOR-verknüpft, im niedrigstwertigen Bit akkumuliert. Dieses Bit ist also genau dann Null, wenn im Eingangswort eine gerade Anzahl von 1-Bits vorhanden war (gerade Parität). Derselbe Prozess funktioniert mit 32-Bit-Ganzzahlen (erfordert jedoch diese beiden zusätzlichen Verschiebungen, die wir in dieser Demonstration übersprungen haben).

Die letzte Codezeile entfernt einfach alle außer dem niederwertigsten Bit (& 1) und dreht es dann um (~x). Das Ergebnis ist dann 1, wenn die Parität des Eingangsworts gerade war, oder sonst null.

GCC hat eingebaute Funktionen dafür:

Eingebaute Funktion: int __builtin_parity (unsigned int x)

Gibt die Parität von zurück xalso die Anzahl der 1-Bits in x modulo 2.

und ähnliche Funktionen für unsigned long und unsigned long long.

Dh diese Funktion verhält sich wie has_odd_parity. Invertieren Sie den Wert für has_even_parity.

Dies sollte die schnellste Alternative auf GCC sein. Natürlich ist seine Verwendung als solche nicht portabel, aber Sie können es in Ihrer Implementierung verwenden, beispielsweise geschützt durch ein Makro.

Die folgende Antwort wurde schamlos direkt abgehoben Bit Twiddling Hacks von Sean Eron Anderson, [email protected]

Berechnen Sie die Wortparität mit einer Multiplikation

Die folgende Methode berechnet die Parität des 32-Bit-Werts in nur 8 Operationen > mit einer Multiplikation.

unsigned int v; // 32-bit word
v ^= v >> 1;
v ^= v >> 2;
v = (v & 0x11111111U) * 0x11111111U;
return (v >> 28) & 1;

Auch für 64-Bit reichen immer noch 8 Operationen.

unsigned long long v; // 64-bit word
v ^= v >> 1;
v ^= v >> 2;
v = (v & 0x1111111111111111UL) * 0x1111111111111111UL;
return (v >> 60) & 1;

Andrew Shapira kam auf diese Idee und schickte sie mir am 2. September 2007.

Versuchen:

int has_even_parity(unsigned int x){
    unsigned int count = 0, i, b = 1;

    for(i = 0; i < 32; i++){
        if( x & (b << i) ){count++;}
    }

    if( (count % 2) ){return 0;}

    return 1;
}

Um die Antwort von TypeIA für jede Architektur zu verallgemeinern:

int has_even_parity(unsigned int x) 
{
    unsigned char shift = 1;
    while (shift < (sizeof(x)*8))
    {
        x ^= (x >> shift);
        shift <<= 1;
    }
    return !(x & 0x1);
}

Die Hauptidee ist dies. Setzen Sie das rechte ‘1’-Bit mit zurück x & ( x - 1 ). Sagen wir mal 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 konvertiert wird 0.

Jetzt x ist 1100. Der Betrieb von x & ( x - 1 )dh, 1100 & 1011 ist 1000. Beachten Sie, dass das Original x ist 1101 und nach zwei Operationen von x & (x - 1) das x ist 1000, dh zwei gesetzte Bits werden nach zwei Operationen entfernt. Wenn nach einem seltsam Anzahl der Operationen, die x Null wird, dann ist es eine ungerade Parität, andernfalls ist es eine gerade Parität.

Hier ist ein eine Linie #define das macht den Trick für a char:

#define PARITY(x) ((~(x ^= (x ^= (x ^= x >> 4) >> 2) >> 1)) & 1) /* even parity */

int main()
{
    char x=3;
    printf("parity = %d\n", PARITY(x));
}

Es ist verdammt portabel und kann leicht modifiziert werden, um mit größeren Wörtern (16, 32 Bit) zu arbeiten. Es ist auch wichtig zu beachten, dass Sie a verwenden #define beschleunigt den Code, jeder Funktionsaufruf benötigt Zeit, um den Stapel zu verschieben und Speicher zuzuweisen. Die Codegröße leidet nicht darunter, insbesondere wenn sie nur wenige Male in Ihrem Code implementiert wird – der Funktionsaufruf kann so viel Objektcode wie die XORs beanspruchen.

Zugegebenermaßen können die gleichen Wirkungsgrade durch Verwendung der erhalten werden in der Reihe Funktionsversion davon, inline char parity(char x) {return PARITY(x);} (GCC) bzw __inline char parity(char x) {return PARITY(x);} (MSVC). Vorausgesetzt, Sie behalten die eine Zeile bei.