Codice Gray
In binario normale, contando da 7 (0111) a 8 (1000) cambiano quattro bit in una volta. Se quei bit vengono letti da un encoder meccanico o campionati da un clock mentre cambiano, può comparire qualsiasi miscuglio di bit vecchi e nuovi, e un 1111 (15) momentaneo è un errore grande. Il codice Gray (binario riflesso) ordina i numeri in modo che valori consecutivi differiscano esattamente di un bit. Lo usano gli encoder rotativi, le mappe di Karnaugh, alcuni ADC e schemi di correzione degli errori.
La conversione è una riga in ogni direzione:
gray = n ^ (n >> 1)
binary = g; while (g >>= 1) binary ^= g; // XOR con tutti gli scorrimenti a destraBCD
Il decimale codificato in binario memorizza ogni cifra decimale nel proprio nibble a 4 bit: 1234 diventa 0001 0010 0011 0100, che come numero hex è 0x1234. Spreca un po’ di spazio (i nibble A–F non vengono mai usati) ma rende banali la visualizzazione decimale e l’aritmetica decimale esatta, per questo lo usano orologi, calcolatrici, il COBOL finanziario e il chip dell’orologio in tempo reale di ogni PC. Leggere un byte BCD come binario puro produce assurdità, ed è l’errore tipico.
Popcount e parità
Il peso di Hamming (popcount) è il numero di bit a 1. È una singola istruzione sulle CPU moderne (POPCNT) e la base della distanza di Hamming, della cardinalità dei bitset e di alcuni trucchi di hashing. La parità è popcount mod 2; un bit di parità è il codice di rilevamento errori più semplice e cattura qualsiasi singolo bit invertito.
// Trucco di Kernighan: ogni passo azzera il bit impostato più basso
int count = 0; while (n) { n &= n - 1; count++; }Domande
Perché gli encoder rotativi usano il codice Gray?
Tra due posizioni adiacenti cambia un solo contatto, quindi una lettura a metà transizione è sempre uno dei due valori vicini, mai uno stravagante. Gli encoder binari possono mostrare qualsiasi valore durante una transizione di più bit.
Il codice Gray è unico?
Il binario riflesso è lo standard, ma qualsiasi ordinamento in cui i vicini differiscono di un bit è «un» codice Gray. Esistono codici Gray bilanciati e n-ari per casi particolari.
Come converto il BCD in binario nel codice?
Prendi ogni nibble come cifra: value = value*10 + nibble, dal nibble più significativo in giù. Oppure, per byte a due cifre, ((b >> 4) * 10) + (b & 0x0F). Molti chip RTC richiedono esattamente questo.
Qual è il modo più veloce per contare i bit?
La funzione integrata: __builtin_popcount (C), bits.OnesCount (Go), int.bit_count() (Python 3.10+), u32::count_ones (Rust). Si compilano in una singola istruzione dove disponibile.