1 Operatori bit-a-bit
(Rev. 2.0.2)La pi` u piccola quantit` a di informazione memorizzabile nella memoria di un computer ` e il bit. Il bit pu` o assumere sono due valori di solito indicati con 1 e 0 anche se, a seconda del loro utilizzo, si anche usano altre rappresentazioni come true/false o yes/no. Tutti i tipi discussi fino ad ora sono rappresentati nella memoria di un computer come una sequenza di pi` u bits, ad esempio il tipo char utilizza una unit` a di otto bits, ossia un byte.
A volte, tuttavia, pu` o risultare utile poter accedere ai singoli bit poich` e la manipolazione dei bits permette una programmazione di livello pi` u basso, e quindi pi` u potente, della program- mazione che utilizza solo tipi. Per contro un programma di basso livello bit-oriented spesso risulta molto meno trasparente di un programma di pi` u altro livello type-oriented.
La programmazione bit-oriented si usa ad esempio per programmi che usano particolari cod- ifiche, come i programmi di compressione, trasmissione ed immagazzinamento dei dati. In fisica la programmazione bit-oriented viene usata spesso quando si utilizzano variabili che possono assumere solo pochi valori, ad esempio due (spin), per cui ` e possibile ridurre la richi- esta di memoria utilizzando i singoli bit, o gruppi di pochi bits, per memorizzare le variabili (multi-spin coding).
1.1 Rappresentazione dei dati binari
Nella programmazione bit-oriented i dati sono sequenze di bits (dati binari), e quindi di difficile lettura per un umano. ` E quindi necessario utilizzare qualche tipo di codifica che li renda pi` u facilmente intellegibili. La codifica pi` u comoda per rappresentare i dati binari ` e il formato esadecimale (hex) poich` e ogni hex-digit fornisce il valore di quattro bits. Ad esempio in questo modo il contenuto di un byte ` e dato da soli due hex-digit.
La seguente tavola riporta la conversione tra la codifica esadecimale e quella binaria.
Tavola conversione hex - binaria hex Binario hex Binario
0 0000 8 1000
1 0001 9 1001
2 0010 A 1010
3 0011 B 1011
4 0100 C 1100
5 0101 D 1101
6 0110 E 1110
7 0111 F 1111
Per le lettere si possono usare anche i caratteri minuscoli: a, b, c, d, e ed f.
Ad esempio se un byte contiene i dati binari “11001000” il suo contenuto nella rappresen-
tazione hex viene ottenuto utilizzando la tavola di conversione dopo aver raggruppato i bits in
gruppi da quattro a partire da desta, per cui nel caso specifico si ha 0xC8. Il prefisso “0x”, o
anche “0X”, ` e necessario per indicare che si tratta di un hex-digit. Siccome per gli hex-digits
si possono usare indifferentemente lettere maiuscole e minuscole avremmo potuto ugualmente scrivere 0xc8.
Se avessimo usato la rappresentazione decimale il contenuto del byte sarebbe stato rappresen- tato da 200, di interpretazione in termini di bits molto meno immediata di quella esadecimale.
Infatti per passare da un numero hex alla rappresentazione binaria ` e sufficiente utilizzare la tavola di conversione associando a ciascun hex-digit la configurazione dei quattro bits cor- rispondenti. Nel caso della rappresentazione decimale invece la conversione richiede divisioni successive per 2. Il vantaggio della rappresentazione esadecimale rispetto a quella decimale per i dati binari ` e quindi evidente.
Operatori bit-a-bit
Per operare sui singoli bits dei dati binari il linguaggio C fornisce sei operatori detti operatori bit-a-bit che possono essere raggruppati in tre categorie:
• Operatori logici bit-a-bit;
• Operatore di complemento bit-a-bit;
• Operatori di shift (traslazione);
I dati binari sono semplici sequenze di bits senza nessuna particolare codifica di conseguenza gli operatori bit-a-bit prendono come operandi solo espressioni a valore di tipo intero int o char. Inoltre poich` e ai bits dei dati binari non ` e associata nessuna particolare codifica questi operatori trattano ogni bit degli operandi individualmente ed indipendentemente gli uni dagli altri, da cui il nome di operatori bit-a-bit.
Sebbene gli operandi degli operatori bit-a-bit possono essere sia con che senza segno per una maggiore sicurezza si consiglia di utilizzare gli operatori bit-a-bit solo con tipi interi senza segno. Infatti il comportamento di questi operatori con i tipi interi con segno pu` o differire da un computer ad un altro soprattutto se il computer non utilizza la rappresentazione in complemento a due per i numeri interi negativi.
1.2 Operatori logici bit-a-bit
I operatori logici bit-a-bit sono in ordine di precedenza:
& ⇒ and
^ ⇒ or esclusivo o xor
| ⇒ or inclusivo o semplicemente or La loro associativit` a ` e a sinistra.
Gli operatori logici bit-a-bit sono operatori binari, ossia prendono due operandi. Il risultato
dell’operatore ` e un dato binario dello stesso tipo degli operandi in cui ciascun bit ` e il risultato
della funzione booleana applicata ai due bits corrispondenti per posizione nei due operandi.
Se gli operandi sono di tipo diverso si applicano le usuali regole di conversione tra tipi ed il risultato sar` a del tipo in cui gli operandi sono stati convertiti.
L’azione degli operatori logici bit-a-bit su ciascun singolo bit ` e:
• L’operatore and “&” restituisce un bit 1 se e solo se entrambi i bits su cui opera sono bit 1, altrimenti restituisce un bit 0
• L’operatore or esclusivo “^ ” restituisce un bit 1 solo nel caso in cui solo uno dei due bits su cui opera ` e un bit 1, altrimenti restituisce un bit 0.
• L’operatore or inclusivo “|” restituisce un bit 1 se almeno uno dei due bits su cui opera
`
e un bit 1, altrimenti restituisce un bit 0.
La loro azione pu` o essere riassunta dalla seguente “tavola della verit` a”:
Operatori Logici Bit-a-Bit
bit 1 bit 2 bit 1 & bit2 bit 1 ^ bit2 bit 1 | bit2
0 0 0 0 0
0 1 0 1 1
1 0 0 1 1
1 1 1 0 1
Gli operatori logici bit-a-bit sono commutativi ed associativi per cui il compilatore ` e libero di riarrangiare le espressioni contenenti questi operatori. Di conseguenza le espressioni con operatori logici bit-a-bit non sono valutate necessariamente nell’ordine con cui sono scritte ma a seconda del compilatore in una delle possibili forme equivalenti.
A prima vista gli operatori logici bit-a-bit sembrano molto simili agli operatori logici “&&”
(and) e “||” (or). Ad esempio se entrambi gli operandi dell’operatore logico “&&” sono true (“non zero”) il risultato sar` a true, allo stesso modo in cui sar` a 1 il risultato dell’operatore logico bit-a-bit “&” se entrambi i bits su cui opera sono 1. Tuttavia nonostante molte simili- tudini gli operatori logici e gli operatori logici bit-a-bit sono operatori diversi. Infatti mentre gli operatori logici operano sul valore degli operandi come un tutt’uno, gli operatori logici bit-a-bit operano su ciascun bit degli operandi indipendentemente.
Per illustrare questa differenza supponiamo di voler controllare se i due numeri interi i e j sono entrambi non nulli. Questo si ottiene facilmente ad esempio come:
if ( ( i != 0 ) && ( j != 0 ) ) {
printf ( " Sono entrambi diversi da zero \n" ) ; }
Alternativamente, siccome un’espressione ` e considerata da un punto di vista logico true se il suo valore ` e non nullo, il controllo pu` o essere effettuato anche come
if ( i && j ) {
printf ( " Sono entrambi diversi da zero \n" ) ;
}
Se in questa seconda versione avessimo usato l’operatore logico bit-a-bit “&” al posto dell’ope- ratore logico “&&” e scritto
if ( i & j ) {
printf ( " Sono entrambi diversi da zero \n" ) ; }
il controllo sarebbe risultato errato. Infatti se i = 1 e j = 2 il test fallisce e il programma non scrive “Sono entrambi diversi da zero”, anche che i numeri sono chiaramente non nulli.
Il motivo ` e che l’operatore logico bit-a-bit opera su ogni bit degli operandi separatamente e non sul valore degli operandi per cui il risultato dell’operazione i & j ` e:
i = 1 00000001 j = 2 00000010 i & j 00000000 ed il test giustamente fallisce.
Osserviamo che se l’operatore logico bit-a-bit “&” fosse stato usato nella prima versione del test
if ( ( i != 0 ) & ( j != 0 ) ) {
printf ( " Sono entrambi diversi da zero \n" ) ; }
invece si avrebbe avuto la risposta corretta. Infatti il risultato dell’espressione logica (i != 0)
`
e il valore booleano 0 o 1 a seconda che l’affermazione sia vera o falsa. Per cui, sebbene l’uso dell’operatore logico bit-a-bit “&” sia improprio in questo contesto, il risultato ` e nonostante tutto corretto poich` e il valore degli operandi dell’operatore bit-a-bit sono sempre convertiti nei valori interi 0 e 1 che differiscono sono per il primo bit. Da questo esempio possiamo concludere che il risultato degli operatori logici bit-a-bit ` e lo stesso degli operatori logici solo se gli operandi sono espressioni a valore booleano 0 o 1.
Vi ` e infine un’altra differenza tra gli operatori logici bit-a-bit e gli operatori logici che a volte pu` o causare errori piuttosto difficili da trovare. Infatti mentre gli operatori logici non valutano l’operando a destra se il valore dell’operando a sinistra ` e sufficiente per determinare se il valore dell’espressione logica ` e true o false, gli operatori logici bit-a-bit valutano sempre entrambi gli operandi.
1.3 Operatore di complemento bit-a-bit
L’operatore di complemento bit-a-bit o negazione bit-a-bit:
~ ⇒ not bit-a-bit o bit flip
`
e un operatore unario che ritorna l’inverso o negazione o complemento bit-a-bit del suo
operando:
• L’operatore “~” restituisce un bit 1 se il suo operando ` e un bit 0 ed un bit 0 se il suo operando ` e un bit 1.
La sua tavola della verit` a ` e quindi semplicemente Complemento
bit ~bit
0 1
1 0
L’operatore di complemento bit-a-bit ` e simile all’operatore logico “!” (not), ma anche in questo caso la somiglianza ` e solo apparente poich` e l’operatore bit-a-bit non opera sul val- ore dell’operando ma indipendentemente su ogni bit della sua rappresentazione binaria. Di conseguenza ogni bit della rappresentazione binaria di di ~e ` e l’inverso di quello che era nell’operando e. Ad esempio se e ` e un tipo intero a 8-bit allora
e = 0xc8 11001000
~e = 0x37 00110111 e = 0xF0 11110000
~e = 0x0F 00001111
Se l’operando dell’operatore unario “~” non ` e di tipo intero, questo viene convertito auto- maticamente ad un tipo intero prima di applicargli l’operatore.
Se l’operando e dell’operatore di complemento bit-a-bit ` e di intero con segno il valore di ~e dipende dalla rappresentazione utilizzata per i numeri interi con segno.
La rappresentazione pi` u utilizzata per gli interi con segno ` e quella di complemento a due.
Ricordiamo che la rappresentazione in complemento a due con n bits del numero intero negativo −i si ottiene aggiungendo 1 al complemento bit-a-bit della rappresentazione binaria con n − 1 bits del numero intero positivo i. In questa rappresentazione il bit pi` u significativo, ossia quello pi` u a sinistra, vale 0 per i numeri positivi e 1 per quelli negativi. Per convincersi di ci` o basta osservare che se ad una stringa di bits si somma il suo complemento bit-a-bit si ottiene una stringa di bits tutti uguali ad 1. Se ora a questa stringa si somma 1 si otterr` a una stringa di bits tutti uguali a 0 ossia la rappresentazione del valore 0. Di conseguenza la stringa con tutti i bits uguali ad 1 ` e la rappresentazione in complemento a due del numero intero negativo −1 e quindi il valore della stringa pi` u il suo complemento bit-a-bit ` e −1 in complemento a due.
Esempio:
Valore i Binario ~i −i Valore −i
72 01001000 10110111 10111000 −72
9 00001001 11110110 11110111 −9
1 00000001 11111110 11111111 −1
0 00000000 11111111 00000000 0
−5 11111011 00000100 00000101 5
Non tutti i computers usano la rappresentazione in complemento a due per gli interi con segno, di conseguenza il valore del risultato dell’operatore di complemento bit-a-bit applicato ad interi con segno pu` o differire da un computer all’altro. Per questo si consiglia di utilizzare l’operatore di complemento bit-a-bit solo con operandi di tipo intero senza segno.
Per un operando e di tipo intero senza segno il valore di ~e ` e UINT MAX - e se il valore di e
`
e, o ` e convertito ad, unsigned int e ULONG MAX - e se invece il valore di e ` e, o ` e convertito ad, unsigned long int. Nello Standard C i valori di UINT MAX e ULONG MAX sono definiti nel file di header di sistema limits.h.
1.4 Operatori di shift
Vi sono due operatori binari di shift (traslazione):
<< ⇒ shift a sinistra left-shift
>> ⇒ shift a destra right-shift
Entrambi gli operatori hanno associativit` a a sinistra ed hanno la stesso livello di precedenza.
Ciascun operatore prende due operandi entrambi di tipo intero e nel caso servisse le usuali regole di conversione sono applicate separatamente ad entrambi gli operandi. Il risultato degli operatori di shift ` e del tipo, o del tipo in cui ` e convertito, l’operando di sinistra.
Il primo operando degli operatori di shift ` e l’oggetto i cui bits vanno traslati mentre il secondo operando ` e il numero di posizioni di cui vanno traslati i bits del primo operando. Il valore dell’operatore ` e uguale al valore del primo operando dopo lo shift. La direzione di traslazione dipende dall’operatore usato. L’operatore left-shift “<<” sposta a sinistra tutti i bits del primo operando del numero di posizioni specificato dal secondo operando. I bits pi` u a sinistra (most-significative) che vengono spostati fuori sono persi, mentre i bits nelle posizioni pi` u a destra (less-significative) che si liberano sono messi a 0. Analogamente, l’operatore right-shift
“>>” sposta a destra tutti i bits del primo operando del numero di posizioni specificato dal secondo operando. I bits spostati fuori a destra sono persi, mentre il valore assegnato ai bits che si liberano a sinistra dipende dal compilatore. Lo Standard C richiede che l’operazione di right-shift sia o logica o aritmetica. Nel primo caso, shift logico, ai bits che si liberano a sinistra viene assegnato il valore di bit 0 mentre nel secondo caso, shift aritmetico, a questi viene assegnato il il valore di bit 0 se l’operando ` e senza segno o il valore del bit pi` u significativo prima dello shift se l’operando ` e con segno. Questo vuol dire che il right-shift aritmetico assegna ai bits che si liberano a sinistra il valore del bit del segno per variabili con segno, e quindi il valore di bit 0 per valori positivi e 1 per valori negativi, ed il valore di bit 0 per le variabili senza segno. Per lo pi` u i compilatori usano un right-shift aritmetico, tuttavia questa duplice possibilit` a fa si che l’uso dell’operatore “>>” con variabili con segno produca programmi generalmente non portabili.
Il valore degli operatori di shift ` e indeterminato se il valore del secondo operando ` e negativo,
per cui uno shift a sinistra di un numero negativo di posizioni non necessariamente risulta
in uno shift a destra, e viceversa. Il risultato pu` o risultare indeterminato anche se il valore
del secondo operando ` e pi` u grande od uguale alla dimensione in bit del primo operando. Se
invece il valore del secondo operando ` e 0 non viene effettuato nessuno shift.
Esempio:
signed char c c = 0x2b 00101011 43 c << 1 c = 0x56 01010110 86 c >> 1 c = 0x15 00010101
a21 c >> 2 c = 0x0a 00001010
a10 c >> 3 c = 0x0a 00000101
a5 (c << 2) >> 2 c = 0xeb 11101011
b−21 c = 0x2b 00101011
c43
a
shift logico o aritmetico
b
shift aritmetico
c
shift logico
Spostare a sinistra di una posizione equivale a moltiplicare per 2, di due posizioni a molti- plicare per 4, e cos`ıvia. Quindi un shift a sinistra di n posizioni ` e equivalente a moltiplicare per 2
n. Se l’operatore left-shift equivale a moltiplicare per 2, l’operatore right-shift equivale alla divisione tra interi per 2, per cui uno shift a destra di n posizioni ` e equivalente a dividere per 2
n. Siccome le operazioni di shift sono pi` u veloci di quelle di divisione e moltiplicazione il compilatore sostituisce quando possibile tutte le divisioni e moltiplicazioni per 2
ncon gli shifts equivalenti.
Come per gli operatori di assegnamento anche per gli operatori bit-a-bit vale la forma con- tratta
var op= expr <==> var = var op expr Ad esempio
i &= j ; /* equivale a i = i & j; */
i <<= 3 ; /* equivale a i = i << 3; */
Esercizi
1. Utilizzando gli operatori bit-a-bit scrivere un programma che stampa i bits di un numero intero sia in formato binario che in formato esadecimale.
c AC 2003
