Gray-Code
Im gewöhnlichen Binärsystem kippen beim Zählen von 7 (0111) auf 8 (1000) vier Bits auf einmal. Werden diese Bits von einem mechanischen Encoder gelesen oder von einem Takt abgetastet, während sie sich ändern, kann jede Mischung aus alten und neuen Bits erscheinen, und ein kurzzeitiges 1111 (15) ist ein großer Fehler. Der Gray-Code (reflektierter Binärcode) ordnet die Zahlen so, dass aufeinanderfolgende Werte sich in genau einem Bit unterscheiden. Drehgeber, Karnaugh-Diagramme, manche ADCs und Fehlerkorrekturverfahren verwenden ihn.
Die Umrechnung ist in jede Richtung ein Einzeiler:
gray = n ^ (n >> 1)
binary = g; while (g >>= 1) binary ^= g; // XOR mit allen RechtsverschiebungenBCD
Binary-coded decimal speichert jede Dezimalziffer in einem eigenen 4-Bit-Nibble: 1234 wird zu 0001 0010 0011 0100, was als Hex-Zahl 0x1234 ist. Das verschwendet etwas Platz (die Nibbles A–F werden nie benutzt), macht aber Dezimalanzeige und exakte Dezimalarithmetik trivial, weshalb Uhren, Taschenrechner, Finanz-COBOL und der Echtzeituhr-Chip in jedem PC es verwenden. Ein BCD-Byte als reines Binär zu lesen ergibt Unsinn, und das ist der übliche Fehler.
Popcount und Parität
Das Hamming-Gewicht (Popcount) ist die Anzahl der 1-Bits. Es ist auf modernen CPUs eine einzelne Instruktion (POPCNT) und die Grundlage von Hamming-Distanz, Bitset-Kardinalität und einigen Hashing-Tricks. Parität ist Popcount mod 2; ein Paritätsbit ist der einfachste fehlererkennende Code und fängt jedes einzelne gekippte Bit.
// Kernighans Trick: jeder Schritt löscht das niedrigste gesetzte Bit
int count = 0; while (n) { n &= n - 1; count++; }Fragen
Warum verwenden Drehgeber Gray-Code?
Zwischen zwei benachbarten Positionen ändert sich nur ein Kontakt, sodass eine Ablesung mitten im Übergang immer einer der beiden Nachbarwerte ist, nie ein wilder. Binäre Encoder können während eines Mehrbit-Übergangs jeden Wert zeigen.
Ist der Gray-Code eindeutig?
Der reflektierte Binärcode ist der Standard, aber jede Anordnung, bei der sich Nachbarn in einem Bit unterscheiden, ist „ein“ Gray-Code. Für Spezialfälle gibt es balancierte und n-äre Gray-Codes.
Wie rechne ich BCD im Code in Binär um?
Jedes Nibble als Ziffer nehmen: value = value*10 + nibble, vom höchstwertigen Nibble abwärts. Oder bei zweistelligen Bytes ((b >> 4) * 10) + (b & 0x0F). Viele RTC-Chips brauchen genau das.
Was ist der schnellste Weg, Bits zu zählen?
Die eingebaute Funktion: __builtin_popcount (C), bits.OnesCount (Go), int.bit_count() (Python 3.10+), u32::count_ones (Rust). Sie werden zu einer einzelnen Instruktion kompiliert, wo verfügbar.