I
dati (numeri interi, numeri reali, caratteri,…) su cui gli elaboratori operano
vengono codificati in quanto possono appartenere ad un qualsiasi insieme.
Iniziamo considerando i sistemi di numerazione per rappresentare interi, reali
e caratteri.
Sistemi di numerazione ed algoritmi di conversione
Un
sistema di numerazione è un metodo che associa ad ogni numero (ente matematico che può essere rappresentato mediante una
stringa di caratteri, detti cifre ,di
un alfabeto fissato) un unico numerale
( sequenza di cifre ). Ad esempio 1621
, MDCXXI sono due numerali per il medesimo numero, appartenenti a due sistemi
di numerazione diversi, rispettivamente la numerazione araba e la numerazione
romana.
MDCXXI è scritto usando un tipo di
sistema additivo, cioè basato su un principio puramente additivo di
numerazione, che usa le cifre I V
X L C M; infatti il numerale in questione rappresenta il valore :
mille+cinquecento+cento+dieci+dieci+uno = milleseicentoventuno. E’ un sistema
non posizionale; quindi di difficile rappresentazione.
1621 è un numerale nel sistema decimale “arabo” che è un sistema di tipo posizionale; cioè ogni cifra ha un peso diverso in base alla sua posizione nella stringa. Infatti noi possiamo scrivere :
1621 = 1x10^3 + 6x10^2 + 2x10^1 +
1x10^0
8,42 = 8x10^0 + 4x10^-1 +2x10^-2
Il peso è calcolato usando una base
che in questo caso è 10 e le cifre sono 0,1,2,…,9.
Apriamo una piccola
parentesi per sottolineare che 1621 è un numero intero senza segno, ossia
formato dai numeri naturali ((1,2,3,….) + lo zero), 8,42 è un numero reale e che
MDCXXI appartiene ai sistemi non posizionali, che hanno regole proprie e per
questo rendono molto complessa l’ esecuzione dei calcoli.
Sistemi
posizionali
In generale consentono di rappresentare i numeri in modo
compatto e per questo i calcoli possono essere effettuati in modo molto
semplice; essi sono distinti dalla base b
.
Un numerale in generale
lo si indica con Cn-1 Cn-2 … C1 C0
dove le cifre Ck Î { 0,1,…,b-1 } con k= 0,…,n-1
Il peso della cifra Ck = b^k con k = 0,1,…,n-1
Numero = Cn-1* b^n-1 + Cn-2*b^n-2 + ...+ C1*b^1 + C0
Il
numero ottenuto con il polinomio in b è rappresentato dal numerale :
(Cn-1 Cn-2 … C1 C0 ) in base b.
Es.
( 1621 ) in base 10 coincide con 1x10^3 + 6x10^2 + 2x10^1 + 1
Il valore di un numero num espresso
nella notazione posizionale e dato dalla seguente formula :
n-1
num = å Ck x b^k
k=0
dove b è la base
e Ck ( con k= 0,1,...,n-1 ) sono le
cifre (comprese fra 0 e b-1)
Una
sequenza di cifre non è interpretabile se non viene precisata la base in cui è
espressa.
Esempi
in tabella di numeri interi:
stringa |
base |
alfabeto |
Calcolo
del valore |
valore |
15 |
2 |
{0,1} |
1*2^3
+ 1*2^2 + 1*2^1+1 |
1111 |
15 |
8 |
{0,1,2,….,7} |
1*8^1
+ 7*8^0 |
17 |
15 |
10 |
{0,1,2…..,9} |
1*10^1
+ 5*10^0 |
15 |
15 |
16 |
{0,1,2,…9,A,…,F} |
0*16^1 +F*16^0 |
0F |
Sistema
binario
Il
sistema binario è posizionale in base
b=2; le cifre o simboli dell’alfabeto sono {0,1}
Il
numero 12 coincide con (1100) in base
2 che è uguale a 12 in base 10.
1100 = 1x2^3 + 1x2 ^2 + 0x2^1 + 0x2^0
è certamente noto che qualsiasi numero elevato a zero fa 1.
I calcoli sono stati eseguiti in base 10.
ßà
Cambiando
base si ottengono altri sistemi significativi in informatica.
Se
b=8 ottengo il sistema ottale costituito dalle cifre
{ 0,1,2,3,4,5,6,7}.
Il
numero 12 in base 10
corrisponde al numero 14 in base 8: infatti è 1x8^1 + 4X8^0
Se
b=16 ottengo il sistema esadecimale costituito dalle cifre :
{
0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F } dove A rappresenta il valore numerico
10, B l’ 11, C il 12, D il 13, E il 14 ed F il 15.
Il
12 in base 16 equivale alla C .
B1F è : 11x16^2 + 1x16^1 +
15x16^0 ossia 2847 in base 10
(20) 16 º (32) 10 º (100000) 2 = ( 40) 8
OSSERVAZIONE
In qualunque sistema posizionale, con cifre
0 per zero e 1 per uno, la base b si rappresenta con ( 10 ) in base b ; ( 10 ) in base 2 = due; (10) in base 8 = otto ; ( 10 ) in base 16
=sedici
Con
1 cifra nei numeri binari si rappresentano due distinti valori 0 ed 1;
con
2 cifre si rappresentano 4 distinti valori { 00 01
10 11 }
con
3 cifre si rappresentano 8 distinti valori { 000 001 010 011 100 101
110 111 }
con n cifre si rappresentano 2^ n valori diversi.
Nei
numeri in base b con n cifre si
rappresentano b^n valori diversi
Operazioni
aritmetiche
Tutte
le notazioni posizionali utilizzano per le operazioni le medesime regole, a
prescindere dalla base di rappresentazione adottata. Per cui le regole che
conosciamo per i numeri decimali restano valide.
Nelle
operazioni con i numeri decimali se eseguiamo la somma fra il numero 26 ed il numero 39 facciamo
26
+
39 =
5
e riporto 1
65
( il riporto in informatica si chiama carry
( pronuncia cherri))
con i numeri binari 1+1 = 0 e riporto 1 per cui 1+1= 10 (che in decimale significa 2)
Tabella
della somma in binario
N1 |
0 |
0 |
1 |
1 |
N2 |
0 |
1 |
0 |
1 |
Somma |
0 |
1 |
1 |
0 |
Riporto |
0 |
0 |
0 |
1 |
Esempi
di somme:
001
+
110 =
111
001 +
101
=
110
011 +
110 =
1001
questa
ultima somma 3 in base 10, + 6 in base dieci fornisce 9 in base 10 , ma per
rappresentare il nove in base due viene richiesta una cifra in più; non bastano
3 bit ma ne necessitano 4; in questo caso si dice che si è verificato un trabocco.
Rappresentazione di un numero con parte frazionaria
( 25.56 ) 10 = 2 * 10^1 +
5 * 10^0
+ 5 * 10^(-1)
+ 6 * 10^(-2)
In
generale, se il numero ha parte frazionaria, dopo C0 ci sono altre cifre di
peso rispettivamente b^(-1) , b^(-2) , … ,b^(-m)
( Cn-1 Cn-2 … C1 C0 C-1 C-2 C-3 C-4
C-5….C-m ) b
Il numero sarebbe:
( Cn-1 * b^(n-1) + Cn-2 * b^( n-2) +…+ C1 * b + C0 +
C-1 *
b^(-1)
+ C-2 * b^(-2) + C-3 * b^(-3) +…+ C-m *
b^ (-m) )
Esempio
( 11001.1001) in base 2 = ( ? ) in base 10
1 * 2^4 + 1 * 2^3 + 0 * 2^2 + 0 * 2^1 + 1 * 2^0 + 1 * 2^(-1) +
0 * 2^(-2)
+ 0 * 2^(-3) + 1 * 2^(-4)
= 16 + 8 + 1 + 0.5 + 0.0625 = ( 25.5625 )
in base 10
è
una rappresentazione approssimata in generale.
Conversioni di base
Esaminiamo le tecniche (algoritmi ) per ottenere un numerale in base b2 che rappresenta un numerale in base b1;
(….….)b1 ® (…........)b2 dove fra parentesi è rappresentato il
medesimo numero.
1) Algoritmo
delle divisioni successive
In
una notazione posizionale:
num = C0 + b^1 * C1 + b^2 * C2 +…..+Cn-1 * b^(n-1)
che si può riscrivere
come :
num=
C0 + b * ( C1 + b * ( C2 + b * ( C3 +...)))
Di conseguenza C0 può essere ricavato come resto della divisione intera fra num/b
per cui il quoziente di tale divisione
è q = C1 +
b*(C2 + b* (C3
+…))
Quindi le altre cifre si ottengono iterando il procedimento, ottenendole
nell’ ordine dalla meno significativa
(LSB) alla più significativa (MSB).
LSB
(least significant bit) MSB (most significant bit).
Cerchiamo di chiarire ciò: se abbiamo un
numero espresso nella base b1 che vogliamo convertire in un numero della base
b2 eseguendo le operazioni tutte in base
b1; procediamo nel seguente modo, che esporremo con un
esempio:
(25) in base 10
deve essere
convertito in un numero ( x ) in base 2.
25 : 2 =12
resto 1 C0 à 1
12 : 2 = 6
resto 0 C1 à 0
6 : 2 = 3 resto 0
C2 à 0
3 : 2 = 1 resto 1
C3 à 1
1 : 2 = 0 resto 1
C4 à 1
per cui il
numero x in base 2 corrispondente al 25 in base 10 è : 11001
Il procedimento che si segue è quindi:
si divide il numero in base b1 per la base b2 ed il resto della divisione intera = C0, poi con il quoziente ottenuto al passo precedente eseguiamo una ulteriore divisione per la base b2 ed il resto = C1, con il quoziente attuale si esegue ancora una divisione per la base b2 ed il resto = C2.. ed il procedimento continua fino ad ottenere un quoziente pari a 0.
Ad ogni divisione fatta
secondo l’ aritmetica della base b1 otteniamo una cifra della rappresentazione
della base b2 ossia si ottiene complessivamente C0, C1, C2,…..,C n-1 .
Quindi per essere più chiari , per
convertire un numero num in base b1=10 in una stringa di cifre in base b2 :
a) si divide num per b2
b) il
resto della divisione costituisce la cifra meno significativa C0;
c) il quoziente serve ad iterare il
procedimento;
d) Se tale quoziente è zero l’ algoritmo
termina, se non è zero tale quoziente lo si assume come nuovo valore num’;
e) Si itera il procedimento con il nuovo valore
num’ .
Esempi
con numeri interi con b1=10
Numero base b1 |
Base b2 |
Calcolo valore |
Stringa |
11 |
2 |
11/2 =5 resto
1 5/ 2 =2 resto 1 2/2
=1 resto 0 1/2
=0 resto 1 |
1011 C3C2C1C0 |
37 |
8 |
37/8 = 4 resto
5 5/8 = 0 resto 5 |
55 C1C0 |
128 |
10 |
128/10 = 12
resto 8 12/10 =
1 resto 2 1/10
= 0 resto 1 |
128 C2C1C0 |
63 |
16 |
63/16 = 3 resto 15 3/16
= 0 resto 3 |
3F C1C0 |
2) L’ espressione che fornisce il numerale
Cn-1*b^n-1+…+ C0 + C-1*b^-1+… fornisce anche un metodo per convertire il
numerale da base b1 a base b2. Infatti per ottenere la rappresentazione nella
base b2 serve esprimere la base b1 ed i coefficienti Ci del numerale su
scritto, nella base b2 e poi eseguire sempre nella base b2, le operazioni
indicate: cioè rappresentare
Ci à ( ...) b2
b1 à (… ) b2
e
poi calcolare il polinomio, facendo i conti in base b2.
Esempio.
( 1100 )2 à (
? )10
( 1100 )2 = (1)2
* (10)^3
2 + (1)2
* (10)^2
2 + (0)2
*(10)^12
+ ( 0 ) 2
* ( 10 )^0 2
= (1)10 * (2)^3 10 + 1 * 2^2 + 0 * 2 + 0
= 1 * 8 + 1 * 4 = ( 12 )10
esempio
( 11001 ) 2 = ( 25 ) 10
1 * 10^4 + 1 * 10^3 + 0 * 10
^2 + 0 * 10^1 + 1*10^0
nella
base 2
= 1* 2 ^4 + 1* 2^3 + 0 + 0 +
1 nella base 10
= 16 + 8 +1 = 25
esempio
( 1100 ) 2 = (
? ) 8
1 * 10^3 + 1 * 10^2 + 0 * 10^1
+ 0 * 10 ^0 base 2
= 1* 2 ^3 + 1* 2^2 base8
otto
quattro
= 1* ( 10 )^1 8 + 4 * (10 )^0 8 = ( 14 ) 8
esercizio
( 31.44 ) 8
= ( 25.5625 ) 10
( 19.9 ) 16 = (
25.5625 ) 10
Il primo si risolve
così :
3* 8 +1 + 4
* 1/8 + 4 *
1/64
il secondo si risolve così:
1 *
16 + 9 + 9 *
1/16
esercizio conversione da base
10 a base due
( 25 ) 10 = ( ? ) 2
= 2 * 10 ^ 1 + 5 * 10 ^0 =
= 10 * 1010 + 101 * 1 = tutto espresso in binario
= 10100 +101 =
=11001
infatti :
1010 *
10 =
_
0000
1010
_
10100
e
10100+
101=
_
11001
Caso di numeri con parte frazionaria ( reali
)
In
questo caso bisogna trattare diversamente la parte frazionaria da quella intera
(
Cn-1 Cn-2 … C1 C0.C-1 C-2… C-m )
Prima
del punto decimale,per la parte intera, eseguiamo n divisioni di (…) in base b1 per ( b2) in base b1;
mentre dopo il punto decimale, per la parte frazionaria, eseguiamo m
moltiplicazioni di (…) in
base b1 per ( b2 ) in base b1.
Infatti
[ C-1*b2^ -1 + C-2 * b2^ -2 +….+ C-m *b2^ -m ] *b2 =
C-1
+ C-2 * b2^ -1 +….+ C-m * b2^ (-m+1)
La
cifra cercata è la parte intera e dopo m moltiplicazioni abbiamo trovato
C-1
C-2 C-3 …. C-m
(
si continua fino a quando il risultato ha parte frazionaria =0 o finchè si
raggiunge una precisione soddisfacente).
Riassumiamo quanto detto in quest’ultima parte: per i numeri interi si opera per divisioni successive, perché gli esponenti sono >= 0 mentre nella parte frazionaria abbiamo esponenti negativi e quindi per isolare le cifre bisogna procedere per moltiplicazioni successive.
La conversione di un numero reale in una stringa avviene in due fasi:
conversione della parte intera ( divisioni successive )
conversione della parte frazionaria ( moltiplicazioni successive ).
L’
algoritmo delle moltiplicazioni successive opera solo su numeri puramente
frazionari (ossia | N |< 1) ; ad ogni passo viene prodotta una nuova cifra della
stringa come l’algoritmo delle divisioni successive, ma in questo caso le
cifre sono prodotte nell’ordine da sinistra a destra ( allontanandosi dal
punto decimale ); la cifra che si produce è disponibile come parte intera del
risultato della moltiplicazione.
Esempio
( 25.5625 )10 = (
…. ) 2
Separiamo parte intera e parte frazionaria:
( 25 )10 = ( 11001 )2 ottenuto
con le divisioni successive
mentre
per
(.5625)10 = ( ? )2 procediamo
usando l’ algoritmo delle moltiplicazioni successive.
.5625
x 2 = 1.125 C- 1
= 1
.125 x 2 = 0.250 C- 2 = 0
.250 x 2 = 0.500 C- 3 = 0
.500 x 2 = 1.000 C- 4 = 1
la
parte frazionaria è uguale a zero e quindi ci fermiamo.
Per
cui la stringa ( ? ) 2
cercata è uguale a 1001
Il numero completo è allora
11001.1001
Primo caso particolare
( Cn-1 Cn-2 … C1 C0 ) in base b^k →( Dm-1 Dm-2 …D1 D0 ) in
base b
Si
traduce ogni cifra Ci in base b
(
[Cn-1 in base b] [Cn-2 in base b] … [C0 in base b] ) in base b
Esempio
( 653 ) in base 8 ® ( ? ) 2
in questo caso k = 3
= ([6 in base 2 ] [ 5
in base 2] [ 3 in base 2])
2
= ( [110] [101] [011] )
= ( 110101011) 2
spiegazione analitica
( … ) in base b^k = Cn-1 * (b^k)^ (n-1) +
Cn-2 * (b^k)^(n-2) +…+C1*b^k + Co
dove Ci Î{0,
1, 2, …, (b^k ) -1}
Si
rappresenta di nuovo tutto in base b
(
Ci ) in base b^k = ( D k-1 ^ i + D k-2
^ i + … + D1 ^ i + D0 ^ i ) in base b
con Dj
^ i Î
{ 0, 1, 2, …, b-1}
“
visto dal punto di vista in base b “ Ci
è un numero compreso tra 0 e (b ^ k) -1
ricordandoci
che con n cifre binarie si rappresentano 2
^ n diversi numeri compresi fra 0 e
2^n - 1, avremo che con n cifre in base b si rappresentano b^n numeri
compresi nell’ intervallo [ 0 , b^n -1] ; quindi per rappresentare un Ci Î [0 ,
b^k -1 ] ci vogliono k cifre.
Allora
ogni cifra Ci Î {0,1, … ,b^k -1}
è rappresentabile come:
Ci = Dk-1 ^ i + Dk-2 ^ i + … + D1 ^ i + D0
^ i
Sostituendo nel polinolimio di (…) in base
b^k otteniamo k * n addendi:
[ Dk-1 ^ (n-1) * b^(k-1) + ..... + D1^ (n-1)*b +D0 ^ (n-1) ] b^(k*(n-1)) +
+ [ Dk-1 ^(n-2) * b^(k-1) + .... + D0 ^
(n-2) ] * b^(k*(n-2)) +
+ ........
+ [ Dk-1 ^ 1 * b^ (k-1) + .... + D0 ^1 ] *
b^k +
+ [ Dk-1 ^ 0 * b^ (k-1) + .... + D0 ^0] =
= Dk-1 ^ (n-1) * b ^ (k-1+k*n -k) + ... +
D1 ^ (n-1) * (b ^ (k * n - k+1))+ D0 ^ (n-1) * b^( k*n - k) + Dk-1 ^ ( n-2) *
b^(k-1+k*n-2k) + ... + D0 ^ (n-2) * b^ (k*n-2k) +
+ ... + Dk-1^(1) * b^(k-1+k) + ... + D0
^(1) * b^k +
+ Dk-1 ^ (0)* b^ (k-1) + ...+ D0 ^
0
CIOE’
(
Cn-1 Cn-2 … C1 C0 ) = ( Dk-1
^ n-1 Dk-2 ^ n-1 ... D1 ^ n-1 D0 ^
n-1 Dk-1 ^ n-2 ... D0 ^ n-2 .........
Dk-1 ^ 0 ... D0 ^ 0 )
Nel termine a primo membro abbiamo n cifre
b^k mentre al secondo membro abbiamo
(Cn-1 ) in base b (Cn-2) in base b …….. ( C0)
in base b.
Esempio
(1
5 A ) in base 16 = ( ? ) in base
2
k=4 per cui ha:
0001
0101 1010 4 cifre binarie per ogni cifra esadecimale
ossia il
numero in base 2 corrispondente al numero in base
16 ( 1 5 A ) è:
(
000101011010 )
Esempio
con numero frazionario
(
25.5 ) in base 10 = ( 11001.1 ) in base 2
000101011010
se
volessimo rappresentare 25.5 in base 8 e 16 dobbiamo considerare il rispettivo
numero binario e
nel caso di base 8 raggruppare a gruppi di k=3
( in quanto 8 è 2^3 ) i bit
iniziando dal punto decimale verso sinistra per la parte intera e dal punto
decimale verso destra per la parte frazionaria; laddove si formano gruppi con
un numero di cifre inferiore a 3 si aggiungono degli zeri.
Nel
nostro caso per la conversione in base 8 avremo 011001.100
= ( 31.4 ) in base 8.
Nel
caso della conversione in base 16 avremo che i gruppi di bit sono k=4 (16 è 2^4) , per cui si ha : 00011001.1000
= ( 19.9 ) in base 16.
Secondo caso particolare
Se b1 = b e b2=b^k come si rappresenta un numero (…) in base b in (…) in base b^k ?
Vale lo stesso ragionamento di prima ma in questo caso invece di espandere, contraiamo la rappresentazione di partenza,
raggruppando cifre della rappresentazione in base b k a k e raggruppando ciascun gruppo in
b^k.
Ossia
in questo caso non è necessario applicare l’ algoritmo di conversione ma si può
agire direttamente.
Esempio
(
110 101 011 ) in base 2 quanto vale in base 8 ?
b1=b=2
e b2=b^k= 2^3
lo
abbiamo gia considerato nell’ esempio precedente per cui si raggruppano i bit a
k a k, 3 a 3 iniziando da sinistra verso destra per cui il numero cercato è (
653 ) in base 8.
Esempio
(
110101011001 ) in base 2 = ( 6531 ) in base 8
(
110101011001 ) in base 2 = ( D59 ) in base 16
calcolarli
come esercizio.
NOTA
BENE
Se
le cifre sono poche per formare i gruppi di bit ne possiamo aggiungere a
sinistra, se il numero rappresentato è
intero , ma devono essere zeri:
avendo 11 001 in base 2 per trasformarlo in base
otto aggiungo uno zero all’ estrema sinistra della stringa ottenendo due gruppi
di k=3 bit ed il risultato è
(
31 ) in base 8.
Se
lo convertiamo in base 16 occorre aggiungere 3 zeri all’estrema sinistra
ottenendo ( 19 ) in base 16.
Richiamo
In
qualunque sistema di numerazione si possono rappresentare numeri con parte
frazionaria
Esempio
11001.1001 ?
=
1 * 2^4 + 1 * 2^3 + 1 * 2 ^0 + 1 * 2^ (-1) + 1 * 2^ (-4)
=
( 25.5625 ) in base 10
Concludendo
abbiamo visto come il metodo delle divisioni successive permette di ricavare da
un numero intero la rappresentazione in base 2 es. ( 25 ) in base 10 è uguale a
( 11001 ) in base 2; simili considerazioni permettono di ricavare (25.5625) in
base 10 come ( 11001.1001 ) in base 2.
Vi
è un trattamento separato della parte intera e della frazionaria.
Per
la parte intera si divide per (b2) in base b1 e si ottengono
CO C1 ... Cn-1.
Per la parte frazionaria moltiplicando per (b2) in base b1 si ottengono :
C-1 C-2 …. C-m .