SOMMARIO

1. Rappresentazione dei numeri in base diversa da 10.
2. La numerazione binaria.
3. Operazioni con i numeri binari.
4. Conversione da decimale a binario.
5. Numerazione «modulo z».
6. Numeri binari negativi.
7. Operazioni logiche.
   1. Operazione «not» (complemento o negazione).
   2. Operazione «and» (congiunzione).
   3. Operazione «or» (disgiunzione).
   4. Altre osservazioni.
8. Opposto di un numero e operazione di sottrazione.
9. Numeri in virgola mobile.

1. Rappresentazione dei numeri in base diversa da 10.

La scelta del numero 10 come base per la nostra numerazione è dovuta a motivi di carattere culturale: la numerazione potrebbe essere basata su un qualunque numero intero maggiore di 1.

Per trattare i numeri occorre un supporto fisico nel quale sia possibile memorizzarli. Ad esempio, una scala graduata consente di far corrispondere a ogni tacca un numero ben preciso (tolleranza a parte), dopo che è stata fissata un'opportuna unità di misura.

Invece negli elaboratori elettronici il dispositivo fisico nel quale si segnano i numeri sono le memorie, che possono essere realizzate in vario modo. Ad esempio, un condensatore può essere carico oppure scarico, un elemento di superficie di un disco può essere magnetizzato oppure smagnetizzato, e così via. In tutti i casi, queste «celle» elementari dispongono di due stati fisici, ai quali vengono attribuiti convenzionalmente i valori di 0 e di 1. Queste sono le «cifre» di cui dispone l'elaboratore per eseguire la numerazione con la massima efficienza.

Dunque il più piccolo elemento di informazione si chiama «bit» e può valere 0 oppure 1. L'informazione è costituita da molti bit disposti in sequenza. Per migliorare la comprensibilità da parte degli esseri umani, si possono considerare le cifre a gruppi e di qui scaturiscono le numerazioni ottale e esadecimale. Schematicamente:

1 bit: numerazione binaria	2 cifre: 0 1
3 bit: numerazione ottale	8 cifre: 0 1 2 3 4 5 6 7
4 bit: numerazione esadecimale	16 cifre: 0 1 2 3 4 5 6 7 8 9 A B C D E F

La numerazione decimale non è affatto comoda per l'elaboratore elettronico perché non può rientrare nello schema precedente (il seguito ne chiarirà il motivo). Provvedono alla conversione particolari programmi che vengono attivati all'accensione dell'elaboratore, senza i quali sarebbe impossibile un'interazione fra l'essere umano e la macchina.

Nel seguito le cifre binarie 0 e 1 saranno scritte in carattere corsivo, mentre i numeri in notazione decimale saranno scritti in carattere normale.

2. La numerazione binaria.

Iniziamo a contare da 0, supponendo di avere a disposizione solo le cifre 0 e 1. Naturalmente possiamo sfruttare il principio posizionale della numerazione, cioè considerare più cifre accostate, ciascuna delle quali assume un valore dipendente dalla posizione occupata nella sequenza (nella numerazione decimale si hanno unità, decine, centinaia, eccetera).

Dopo aver contato 0 e 1, viene il «due» (scritto in parola perché non esiste una cifra che lo descrive): rappresentiamo questo numero con 10, cioè una «duina» e zero «unità». Proseguendo il conteggio si ha:

0
1
10
11
100
101
110
111
...

Ogni volta che si incrementa di una unità, la cifra più a destra diventa 1 se era 0, mentre se era 1 diventa 0 e fa scattare la cifra adiacente, proseguendo con il riporto verso sinistra fino a che non si trova una cifra uguale a 0 (se necessario, allorché si incontra una posizione vuota la si interpreta come 0 e la si fa diventare 1).

La prossima tabella mostra i numeri da zero a diciassette, nella colonna di sinistra in forma decimale e in quella di destra in forma binaria:

numero decimale		numero binario
0		0
1		1
2		10
3		11
4		100
5		101
6		110
7		111
8		1000
9		1001
10		1010
11		1011
12		1100
13		1101
14		1110
15		1111
16		10000
17		10001
...		...

Dunque, partendo da destra, le cifre di un numero in forma binaria rappresentano il numero di «unità», di «duine», di «quattrine», di «ottine», di «sedicine», e così via, che ogni volta può essere 0 oppure 1. In altri termini, ogni posizione indica la presenza o l'assenza di una quantità doppia di quella che le sta alla destra, cioè tali quantità sono espresse dalle potenze di due. Alcuni esempi:

potenza		numero decimale		numero binario
20		1		1
21		2		10
22		4		100
23		8		1000
24		16		10000
25		32		100000
26		64		1000000

eccetera (il comportamento è analogo a quello della numerazione decimale, dove però le posizioni corrispondono alle potenze di dieci).

Ad esempio, interpretiamo il numero binario 110101, ponendo sotto ciascuna cifra la relativa potenza (che corrisponde alla posizione della cifra nel numero dato):

1	1	0	1	0	1
25	24	23	22	21	20

Ciò mostra che è facile determinare il valore decimale di tale numero. Indicando con un asterisco l'operazione di moltiplicazione, si ha:

110101 binario =	1 * 25 + 1 * 24 + 0 * 23 + 1 * 22 + 0 * 21 + 1 * 20 =
=	1 * 32 + 1 * 16 + 0 * 8 + 1 * 4 + 0 * 2 + 1 * 1 =
=	32 + 16 + 0 + 4 + 0 + 1 =
=	53 decimale

Per la conversione di un numero decimale in forma binaria conviene prima fare qualche altra considerazione sulle operazioni.

3. Operazioni con i numeri binari.

In sostanza abbiamo già visto come si fa per sommare 1 a un dato numero binario. Analogamente si procede per sommare fra loro due numeri binari qualsiasi: dopo averli scritti con l'incolonnamento corretto (le unità sotto le unità e così via andando da destra a sinistra), si somma tenendo conto che:

• 0 + 0 = 0
• 0 + 1 = 1
• 1 + 1 = 0 con riporto di 1

Se c'è un riporto, esso va aggiunto alla colonna immediatamente a sinistra. In base alle due cifre presenti in tale colonna, tenendo conto del riporto 1, si hanno i seguenti casi:

• entrambe le cifre sono 0:
  nel risultato si scrive 1 (senza ulteriore riporto);
• una cifra è 0 e l'altra è 1:
  nel risultato si scrive 0 con riporto di 1;
• entrambe le cifre sono 1:
  nel risultato si scrive 1 con riporto di 1.

Così si procede fino a quando le cifre di entrambi i numeri sono esaurite.

Per quanto riguarda la moltiplicazione, dedichiamo particolare attenzione solo alla moltiplicazione per le potenze di due (il procedimento di calcolo è del tutto simile a quello che si esegue con i numeri decimali).

Moltiplicare per due un numero scritto in forma binaria significa che le unità diventano «duine», queste diventano «quattrine» e così via: ciò significa spostare di un posto verso sinistra tutte le cifre, scrivendo 0 nella posizione delle unità.

Se invece si moltiplica per quattro (che è uguale alla potenza 2², cioè il numero binario 100) si spostano tutte le cifre verso sinistra di due posti; se si moltiplica per otto (cioè 2³, binario 1000) di tre posti, e così via. In generale la moltiplicazione per 2ⁿ (in forma binaria dato da 1 seguito da n zeri) consiste nello spostare le cifre di n posti verso sinistra, riempiendo con n zeri i posti lasciati vuoti.

Inversamente si può eseguire la divisione per una potenza di base due ed esponente n, purché il numero binario termini con almeno n zeri: si spostano tutte le cifre verso destra di n posti, eliminando gli n zeri più a destra. Ad esempio, la divisione del numero binario 11000 per quattro dà come risultato 110 (sono stati eliminati i due zeri più a destra).

La sottrazione pone un problema, collegato con la rappresentazione dei numeri negativi, per i quali occorre trovare il modo di rappresentare il segno «-». Ciò richiede una convenzione che sarà spiegata più avanti.

4. Conversione da decimale a binario.

Dalle considerazioni precedenti si deduce che la cifra più a destra di un numero pari è sempre 0 e, di conseguenza, la cifra più a destra di un numero dispari è sempre 1.

Il procedimento per convertire in forma binaria un certo numero decimale n consiste nello scrivere, andando da destra verso sinistra, le cifre 0 oppure 1 determinate con le regole descritte qui di seguito:

1. se n è pari si scrive 0;
2. se n è dispari si scrive 1 e si sostituisce n con n-1;
3. essendo n pari (nel secondo caso lo è diventato), si divide n per due e si riprende il procedimento dal primo passo prendendo come n questo nuovo valore.

Dopo un certo numero di iterazioni si arriva a 0 e il procedimento ha termine.

Esempio. Scriviamo in forma binaria il numero decimale 171 (le operazioni nella parte sinistra sono fatte con numeri decimali; sulla destra scriviamo le cifre binarie che determiniamo progressivamente).

171 è dispari: 171-1=170 170 diviso 2 = 85	scriviamo 1
85 è dispari: 85-1=84 84 diviso 2 = 42	scriviamo 1
42 è pari: 42 diviso 2 = 21	scriviamo 0
21 è dispari: 21-1=20 20 diviso 2 = 10	scriviamo 1
10 è pari: 10 diviso 2 = 5	scriviamo 0
5 è dispari: 5-1=4 4 diviso 2 = 2	scriviamo 1
2 è pari: 2 diviso 2 = 1	scriviamo 0
1 è dispari: 1-1=0 (termine del procedimento)	scriviamo 1

Più sinteticamente:

171	|	1
85	|	1
42	|	0
21	|	1
10	|	0
5	|	1
2	|	0
1	|	1
0	|

Leggendo dal basso verso l'alto le cifre della colonna di destra, si ottiene che 171 decimale equivale a 10101011 binario.

In conclusione:

un numero in forma binaria si esprime come una successione di cifre, che sono anche dette bit (in inglese «bit» significa «pezzetto» o «particella»).
La cifra più a destra è quella «meno significativa» (lsb), cioè rappresenta quantità più piccole, quella più a sinistra è la «più significativa» (msb).

Osservazione. Il minimo numero di bit necessari per rappresentare un numero intero n>0 è il logaritmo in base 2 di n, valore che va arrotondato all'intero immediatamente superiore. In formula (dove LOG2 è il logaritmo in base 2 e INT è la funzione parte intera):

numero_bit = 1 + INT(LOG2(n))

La stessa formula, usando il logaritmo naturale LOG, diventa: s

numero_bit = 1 + INT(LOG(n) / LOG(2))

In altri termini, occorre determinare la più piccola potenza di 2 che è maggiore di n: il risultato è l'esponente di tale potenza.

5. Numerazione «modulo z».

La nostra immaginazione ci consente di considerare l'esistenza di numeri arbitrariamente grandi, disposti su di una retta idealmente illimitata. Invece per «memorizzare» i numeri su un qualunque supporto fisico vanno adottate delle limitazioni (ad esempio, la lunghezza finita del righello su cui si riportano le tacche dei numeri, la grandezza della memoria elettronica, eccetera).

In particolare, in un elaboratore elettronico occorre stabilire quanto spazio (cioè quanti bit) dedicare a ogni numero che si vuole utilizzare. Tale limitazione è necessaria, pur potendo variare la sua entità a seconda del contesto.

Supponiamo di avere a disposizione n bit: il primo consente due alternative, per ognuna di esse il secondo bit consente due alternative, e così via fino al bit n-esimo. Complessivamente le possibilità sono:

2 * 2 * ... * 2 (n volte) = 2ⁿ

Ad esempio:

• una sequenza di 8 bit è chiamata «byte» o anche «char»: con un byte è possibile rappresentare 2⁸=256 numeri;
• una sequenza di 16 bit, cioè due byte affiancati, è chiamata «integer» e permette di rappresentare 2¹⁶=65536 numeri;
• una sequenza di 32 bit (o quattro byte) è chiamata «long» e permette di rappresentare 2³²=4294967296 numeri.

Qui faremo le nostre considerazioni solo per i numeri rappresentabili come integer, ma il tutto si può ripetere per gli altri tipi di dati apportando pochi semplici adattamenti.

Come nella numerazione decimale, è consuetudine tralasciare le eventuali cifre 0 iniziali (a sinistra), a meno che non sia importante evidenziare quante sono le cifre utilizzabili. Così il numero binario 111 corrisponde al numero decimale 7 per tutti e tre i tipi di numeri suddetti (char, integer e long).

Supponiamo per un momento di eseguire il conteggio partendo da 0 e di poter scrivere via via tutti i numeri consecutivi in forma binaria, senza alcuna limitazione.

Così, dopo 32767=2¹⁵-1 passi, troviamo il numero x = 0111111111111111 (la cifra iniziale 0, che è seguita da quindici cifre 1, potrebbe essere omessa). Il successore di x è y = 1000000000000000 (1 seguito da quindici 0), cioè si ha x+1=y. Infatti:

0111111111111111	+
1	=
1000000000000000

Proseguendo ancora, dopo altri 32767 passi troviamo il numero binario costituito da sedici cifre uguali a 1 (al quale per ora non diamo un nome) e il suo successore z = 10000000000000000 (1 seguito da sedici 0). Il procedimento potrebbe continuare, ma ci fermiamo qui.

Nell'insieme di numeri che abbiamo scritto (da 0 a z) ce n'è uno di troppo, dato che per la rappresentazione di questi 65537 numeri abbiamo solo 2¹⁶=65536 posti, consentiti dalle 16 cifre binarie a nostra disposizione. Allora siamo costretti a lasciar fuori l'ultimo valore z? Facciamo così: «identifichiamo» z con il numero 0.

Il risultato del procedimento può essere descritto come segue:

ciascuno dei numeri considerati è stato contrassegnato con una tacca su di una fettuccia flessibile, che è stata poi piegata a forma di circolo, in modo da far combaciare gli estremi, dove erano stati posti rispettivamente i valori 0 e z.

Il conteggio dei numeri così disposti è dunque ciclico: partendo da un qualunque numero k, dopo z passi ritroviamo il numero k di partenza.

La particolare numerazione descritta è detta «numerazione modulo z»: in essa due numeri che differiscono per un multiplo intero di z sono considerati lo stesso numero. Ad esempio, i numeri 6, 16, 96, -14 sono lo stesso numero nella numerazione modulo 10.

6. Numeri binari negativi.

I numeri binari di 16 cifre, interpretati come nel paragrafo precedente, sono detti «unsigned integer», cioè integer privi di segno, dato che rappresentano numeri non negativi.

Se occorre utilizzare anche numeri negativi, come accade normalmente, si deve suddividere l'insieme in due parti, ciascuna delle quali è composta da 2¹⁵=32768 elementi:

• insieme P dei numeri con primo bit (msb) uguale a 0:
  da 0 a x (0 e numeri positivi);
• insieme N dei numeri con primo bit (msb) uguale a 1:
  da y a z-1 (numeri negativi).

Il bit più significativo (il primo a sinistra nella rappresentazione binaria) distingue così i numeri dell'insieme P da quelli dell'insieme N. Perciò si usa dire che tale bit rappresenta il «segno» del numero integer (il segno è 1 esattamente quando il numero è negativo).

Ma c'è un'apparente contraddizione. Nel precedente paragrafo i numeri binari dell'insieme N corrispondevano ai numeri decimali:

32768   ...   65535

Come mai è legittimo interpretare tali numeri come negativi? Per il semplice motivo che, considerati «modulo z», essi sono la stessa cosa. Infatti, sottraendo z (decimale 65536) dai numeri di sopra, si ottengono nell'ordine i numeri:

-32768   ...   -1

Dunque gli integer con segno variano fra il minimo y (decimale -32768) e il massimo x (decimale 32767).

Naturalmente le limitazioni poste impongono di controllare che non si eccedano i limiti consentiti. Ad esempio, operando con numeri integer con segno non è lecito considerare il numero x+1, cioè il successore di x. Se un programma tentasse di utilizzare tale numero, si genererebbe una situazione di errore detta «overflow» (eccesso).

Notare che il numero decimale 65535 può essere rappresentato come unsigned integer, mentre -1 può essere rappresentato come integer con segno: entrambi questi numeri corrispondono alla sequenza di sedici bit 1.

Va anche osservato che le operazioni algebriche con numeri integer negativi funzionano in modo coerente. In particolare vale la seguente operazione di somma binaria (che tradotta in forma decimale significa «-1+1=0»):

1111111111111111	+
1	=
0000000000000000

Notare che, se non ci fossero limitazioni nel numero di bit, il risultato della somma precedente dovrebbe essere il numero binario di diciassette cifre 10000000000000000 (cioè la cifra 1, che scaturisce dai riporti, seguita da sedici cifre 0). In realtà si agisce proprio in questo modo, ma viene scartata la cifra 1, scivolata nella diciassettesima posizione (contando da destra), grazie all'identificazione fra i numeri 0 e z che, modulo z, hanno lo stesso valore.

Un altro esempio è dato dalla seguente somma, che esprime in forma binaria l'operazione x+y=-1:

0111111111111111	+
1000000000000000	=
1111111111111111

7. Operazioni logiche.

Parlando di operazioni logiche (dette anche operazioni «booleane»), è utile attribuire il significato di «vero» al bit 1 e di «falso» al bit 0 (si usano anche i termini «bit alto» per 1 e «bit basso» per 0).

Ciascuna operazione logica viene dapprima definita prendendo come operandi i singoli bit (uno o due operandi, a seconda dell'operazione): i risultati per i vari casi vengono posti in una tabella, detta «tabella di verità».

Successivamente si estende l'operazione a operandi binari di lunghezza qualsiasi, applicando la tabella di verità ai singoli bit; se gli operandi sono due, essi devono avere la stessa lunghezza e l'operazione si applica via via ai bit che nei due operandi occupano la stessa posizione.

8. Opposto di un numero e operazione di sottrazione.

Supponiamo di avere la rappresentazione binaria di un integer n e di voler determinare quella del suo opposto -n, cioè del numero che sommato a n dà come risultato 0.

Consideriamo i numeri integer 0 (sequenza di sedici bit 0) e -1 (sequenza di sedici bit 1). Partendo da 0 scriviamo via via i successori (colonna di sinistra), mentre partendo da -1 scriviamo i predecessori (colonna di destra) (per semplicità scriviamo solo otto bit invece di sedici):

00000000		11111111
00000001		11111110
00000010		11111101
00000011		11111100
00000100		11111011
00000101		11111010
00000110		11111001

e così via. Si nota che in ogni riga i numeri di sinistra e di destra sono sempre l'uno il complemento dell'altro. Ciò dice che, fatti m passi, vale la seguente uguaglianza:

not (0 + m) = -1 - m

Posto m = n - 1, la precedente uguaglianza diventa:

not (n - 1) = - n

cioè l'opposto -n di n si ottiene diminuendo n di una unità e passando al complemento.

Si può verificare che questa regola funziona anche quando n è un numero negativo: fa eccezione unicamente il numero y, il minimo integer, del quale non è possibile calcolare l'opposto -y perché non esiste il predecessore del minimo numero ammesso.

Sapendo determinare l'opposto di n, è possibile eseguire la sottrazione m-n: basta sommare a m l'opposto di n, determinato come sopra.

9. Numeri in virgola mobile.

Naturalmente può verificarsi il caso che il risultato di un'operazione ecceda le limitazioni poste dal tipo di dati considerati. È uno dei compiti del programmatore utilizzare il tipo di dati più appropriati per gli impieghi previsti.

Per limitare le possibili situazioni di overflow, si usano rappresentazioni numeriche dette «in virgola mobile». In sostanza un numero viene rappresentato come la moltiplicazione di un primo numero che ha una parte intera e una parte frazionaria e di un secondo numero che è una potenza di 10. Si usa indicare la potenza con scritture del tipo E+12 (in luogo di 10¹²) o E-17 (in luogo di 10^-17).

Se da un latoquesta tecnica consente di utilizzare numeri molto grandi o molto vicini a 0, dall'altro obbliga a un'approssimazione che in ogni caso introduce un errore più o meno grande.

Ad esempio, usando sequenze di 32 bit (cioè quattro byte) il numero «pi greco» può essere approssimato come 3.141593 (invece di 3.141592653589...). In compenso è possibile eseguire operazioni con numeri grandi, come ad esempio:

5.923124E+12 * 4.761349E+09 = 2.820206E+22

La rappresentazione dei numeri in virgola mobile come sequenze di bit 0 e 1 è complessa e può essere realizzata in più modi (formati MBF e IEEE): in ogni caso è al di là degli scopi di questa trattazione.

I tipi più comuni di strutture di dati in virgola mobile sono:

• precisione singola o «real» (4 byte, cioè 32 bit);
• precisione doppia o «double» (8 byte, cioè 64 bit).