Aritmetica binaria in C
Da PtLUG Wiki.
Contents |
Introduzione
Nella programmazione a basso livello molto spesso capita di dover modificare o verificare i singoli bit di uno o piu' byte. Per compiere queste operazioni è necessario avere una buona dimestichezza con l'aritmetica binaria e con i relativi operatori, che normalmente non siamo abituati ad utilizzare in altri linguaggi di piu' alto livello.
Gli operatori binari
Gli operatori binari sono i seguenti:
- ~ (NOT): Inverte una maschera di bit, ad esempio trasformando 0 0 0 1 0 1 0 0 in 1 1 1 0 1 0 1 1. La tabella di verità è la seguente:
A | ~ ----- 1 | 0 0 | 1
Restituisce 0 quando l'operando vale 1 e viceversa.
- & (AND): l'operatore AND lavora secondo la seguente tabella di verità:
A | B | & --------- 1 | 0 | 0 0 | 1 | 0 0 | 0 | 0 1 | 1 | 1
ovvero restituisce 1 solo quando entrambi gli operandi sono a 1.
- | (OR): l'operatore OR lavora secondo la seguente tabella di verità:
A | B | | --------- 1 | 0 | 1 0 | 1 | 1 0 | 0 | 0 1 | 1 | 1
ovvero restituisce 0 solo quando entrambi gli operandi valgono 0 e restituisce 1 in tutti gli altri casi.
- ^ (XOR): l'operatore XOR è anche detto OR esclusivo ed opera secondo la seguente tabella:
A | B | ^ --------- 1 | 0 | 1 0 | 1 | 1 0 | 0 | 0 1 | 1 | 0
ovvero restituisce 1 solo quando gli operatori sono diversi fra loro e 0 quando sono uguali.
- >> (SHIFT DX): sposta i bit da sinistra verso destra.
- << (SHIFT SX): sposta i bit da destra verso sinistra.
Maschere di bit
Per poter modificare solo determinati bit di un byte, è necessario costruirsi un'opportuna maschera di bit, da utilizzare come operando. Se ad esempio volessimo modificare il bit 3 di un byte, dovremmo avere una maschera di bit costruita nel seguente modo:
0 0 0 0 1 0 0 0
I bit ovviamente si contano da 0 a 7, quindi il 3° bit sarà nella posizione 4.
Per ottenere una maschera simile, occorre partire dalla maschera che rappresenta il numero 1:
0 0 0 0 0 0 0 1
e spostare il bit 0 verso sinistra di tante volte quanto il numero che vogliamo settare. Ad esempio, per avere il bit 3 settato a 1, dobbiamo spostare a sinistra l'1 di 3 posizioni, mediante l'operatore <<
In C dovremmo scrivere
int a = 1; a <<= 3;
Settare un bit
Il meccanismo basilare quando si vuole settare un bit è quello di costruirsi una maschera di bit contenente tutti zeri eccetto il bit che si vuole settare. A questo punto bisogna fare applicare l'operatore OR fra i byte originali e la maschera appena costruita. L'OR fra il bit che vale 1 ed il corrispettivo bit del byte originale, imposterà tale bit ad 1, mentre tutti gli altri rimarranno invariati.
0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 --------------- 0 1 0 1 0 0 1 0
I bit risultanti sono rimasti invariati eccetto quello che volevamo settare.
Resettare un bit
Per resettare un bit, ovvero per mettere un bit a zero, occorre fare l'operazione praticamente inversa rispetto a quella precedente. Per prima cosa, ottenuta la maschera di bit 0 0 0 0 1 0 0 0 andrà negata con l'operatore ~ diventando così 1 1 1 1 0 1 1 1. A questo punto applicando l'AND fra i bit di partenza e la nuova maschera di bit, lasceremo invariati tutti i bit eccetto quello in corrispondenza dello zero:
1 0 1 0 1 1 0 1 1 1 1 1 0 1 1 1 --------------- 1 0 1 0 0 1 0 1
Invertire un bit
A volte, può capitare la necessità di invertire lo stato di uno o più bit, senza conoscere a priori lo stato dei bit in questione. Il caso d'uso tipico è legato alle funzioni di toggle: premo un pulsante e si inverte lo stato, qualunque esso sia. Per fare questo, è necessario ottenere una maschera con a 1 i bit che ci interessa togglare. Poi è sufficiente applicare l'operatore XOR (^): i bit che nella maschera erano a 0 saranno lasciati invariati, quelli che nella maschera erano a 1 avranno il loro stato invertito:
1 0 1 0 1 1 0 1 0 0 0 0 1 0 0 0 --------------- 1 0 1 0 0 1 0 1
Da notare che applicando 2 volte l'operatore XOR con la stessa maschera si riottiene il dato di partenza. E' per questo che l'operatore XOR è uno dei più semplici sistemi di crittografia usati.
Verificare se un bit è settato
Per verificare se un bit è settato a 1 occorre fare l'AND con una maschera che abbia tutti zeri eccetto quel bit da verificare. Se il valore corrispondente alla maschera risultante conterrà tutti zeri, il bit era a zero. Se il valore complessivo della maschera sarà diverso da zero, il bit era a 1. Supponiamo di voler verificare se 0 0 0 1 0 0 1 0 ha il 3° bit settato:
0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 --------------- 0 0 0 0 0 0 0 0
Ottenendo complessivamente zero, possiamo affermare che il 3° bit era a zero. Verifichiamo adesso 0 0 0 1 1 0 1 0:
0 0 0 1 1 0 1 0 0 0 0 0 1 0 0 0 --------------- 0 0 0 0 1 0 0 0
Essendo il valore complessivo diverso da zero, possiamo affermare che il 3° bit era a uno.
Autore
Questo articolo è stato scritto da Andrea Grandi.
Ringraziamenti
Un ringraziamento particolare a Francesco Sacchi (Batt) che mi ha delucidato notevolmente sull'aritmetica binaria e su come utilizzarla nel linguaggio C.
