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

Lesezeit: 6 Minuten

Benutzeravatar von Manuel
Manuel

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
}

  • Mögliches Duplikat des Bitparitätscodes für eine ungerade Anzahl von Bits

    – Troyseph

    27. Oktober 2015 um 9:58 Uhr

  • Siehe hier: stackoverflow.com/questions/21589674/even-parity-of-a-unsigned-int.

    – Troyseph

    27. Oktober 2015 um 10:03 Uhr


  • Der allgemeinere (und langsamere) Fall ist Zählen Sie die Anzahl der gesetzten Bits in einer 32-Bit-Ganzzahl

    – Peter Mortensen

    26. August um 20:12 Uhr


  • Eine Frage aus dem Jahr 2010: Was ist der schnellste Weg für Bitoperationen, um eine Parität zu berechnen?

    – Peter Mortensen

    26. August um 21:33 Uhr

Benutzeravatar von TypeIA
TypIA

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.

  • Die letzte Codezeile dreht Bits um und entfernt dann die anderen Bits (Ihre Erklärung hat diese beiden umgekehrt)

    – MM

    17. August 2017 um 4:13 Uhr

  • Und bei einem 8-Bit-Wert wären es nur die letzten drei XOR-Zeilen (statt der fünf XOR-Zeilen)?

    – Peter Mortensen

    29. August um 23:19 Uhr


Antti Haapala -- Benutzeravatar von Слава Україні
Antti Haapala – Слава Україні

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.

  • Anstatt das Rad in verschiedenen Formen und Größen neu zu erfinden, halte ich dies für den besten Ansatz.

    – faruk13

    5. Juli 2019 um 17:05 Uhr

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.

Benutzeravatar von γηράσκω δ' αεί πολλά διδασκόμε's
γηράσκω δ’ αεί πολλά διδασκόμε

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

Benutzeravatar von HungryFoolish
HungrigDumm

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

  • Das ist nichts für Architektur.

    – Antti Haapala – Слава Україні

    31. Dezember 2017 um 9:18 Uhr

Benutzeravatar von Peter Mortensen
Peter Mortensen

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.

  • Das ist nichts für Architektur.

    – Antti Haapala – Слава Україні

    31. Dezember 2017 um 9:18 Uhr

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.

  • Dies ist nicht ganz korrekt, es sollte verwendet werden vorzeichenlose Zeichennicht unterschrieben

    – Antti Haapala – Слава Україні

    6. Juli 2019 um 4:07 Uhr

  • Oppsis, du hast recht, danke. Ich werde den Beitrag jedoch nicht ändern, es wird trivial für diejenigen sein, die es verwenden, um es zu beheben (oder nicht).

    – Danny Holstein

    7. Juli 2019 um 21:38 Uhr


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

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy