La rappresentazione dei Numeri

Numeri interi non negativi (numeri naturali + lo zero)

Rappresentabili con diverse notazioni:

• additiva romana: I, II, III, IV, V, .... IX, X, XI...
• posizionale araba: 1, 2, .. 10, 11, ... 100, ...

Notazioni additiva

in una notazione additiva, si procede per confronti e/o applicando complesse regole (strettamente dipendenti dalla rappresentazione)

esempio: convertire 27 in notazione romana

conclusione: 27 si rappresenta in romano con la stringa di simboli XXVII

Notazioni posizionali

Nella rappresentazione posizionale è fondamentale il concetto di base di rappresentazione B.

Il valore di un numero n espresso in questa notazione è dato dalla formula:

 n = d₀ *B⁰ + B¹ * d₁ + B² * d₂ + B³ * d₃ + ...

che si può riscrivere come

n-1

n = S d_k * B^k

k=0

dove:

• B è la base
• i d_k (k=0..n-1) sono le cifre (comprese fra 0 e B-1) della stringa che rappresenta il numero.

Osservazioni

Una stringa di cifre non è interpretabile se non si precisa la base su cui è espressa.

Ogni numero è esprimibile in modo univoco in una qualunque base

Esempi

 
 

Stringa	Base	Calcolo valore	Valore in base 10
12	4	4 * 1 + 2	6
12	8	8 * 1 + 2	10
12	10	10 * 1 + 2	12
12	16	16 * 1 + 2	18

 

Casi di particolare interesse:

base B=2 ® due sole cifre: 0 e 1

base B=8 ® otto cifre: 0, 1, 2, 3, 4, 5, 6, 7

base B=10 ® dieci cifre: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

base B=16 ® sedici cifre: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F

10 11 12 13 14 15

Conversioni di rappresentazione da base B a base 10

Ogni numero è espresso, in una base data, da una ben precisa sequenza di cifre

Data una rappresentazione sotto forma di sequenza di cifre (e una base), il numero corrispondente si ricava applicando la formula già vista:

n = d₀ *B⁰ + B¹ * d₁ + B² * d₂ + B³ * d₃ + ...

che si può anche scrivere:

k=0

ma come effettuare la conversione inversa?

Ovvero:

dato un numero in base 10, come si ricava la sua rappresentazione sotto forma di sequenza di cifre in una base B assegnata?

Osservando che comunque in una notazione posizionale si ha

n = d₀ *B⁰ + B¹ * d₁ + B² * d₂ + B³ * d₃ + ...

ovvero

n = d₀ + B *( d₁ + B¹ * d₂2 + B² * d₃3 + ... )

che si può riscrivere come:

n = d₀ + B *( d₁ + B¹ * (d₂ + B² * (d₃ + ... ))))

possiamo applicare il seguente Algoritmo di conversione detto "Algoritmo delle divisioni successive"

d₀ si può ricavare come resto della divisione intera n / B

il quoziente si esprime come q = d₁ + B¹ * (d₂ + B² * (d₃ + ... ))))

Le altre cifre si possono ottenere allo stesso modo, iterando il procedimento

NOTA: l’algoritmo fornisce le cifre da quella meno significativa a quella più significativa

Algoritmo di conversione

Per convertire il numero n in una stringa di cifre che ne rappresentino il valore in base B

1. Dividi n per B

1.1 il resto costituisce la cifra meno significativa (LSB - Least Significant Bit )

1.2 il quoziente serve a iterare il procedimento

Esempi di rappresentazioni in diverse basi

 
 

B=10	B=2	B=8	B=16
1	1	1	1
2	10	2	2
3	11	3	3
4	100	4	4
5	101	5	5
8	1000	10	8
10	1010	12	A
15	1111	17	F
16	10000	20	10
31	11111	37	1F
32	100000	40	20
100	1100100	144	64
255	11111111	277	FF

 

Osservazione

Le rappresentazioni R1 e R2 di uno stesso numero su basi B1 e B2 che sono una potenza dell’altra sono strettamente correlate:

se B1=2 e B2 = 2ⁿ, ogni cifra nella rappresentazione R1 corrisponde a n cifre nella rappresentazione R2 in particolare:

• ogni cifra esadecimale corrisponde a 4 cifre binarie
• ogni cifra ottale corrisponde a 3 cifre binarie

Conseguenza

Per passare dalla rappresentazione di un numero in base B1 a quella in base B2 (o viceversa) non è necessario applicare l’algoritmo di conversione, ma si può agire direttamente sostituendo ordinatamente ogni cifra di R1 con gruppi di n cifre di R2.

Esempi
 

Rappr. Base 2	Suddiv Rappr. Base 8	Rappr. Base 8	Suddiv Rappr. Base 16	Rappr. Base 16	Rappr.  Base 10
1	1	1	1	1	1
10	10	2	10	2	2
11	11	3	11	3	3
100	100	4	100	4	4
101	101	5	101	5	5
1000	1 000	1 0	1000	8	8
1010	1 010	1 2	1010	A	10
1111	1 111	1 7	1111	F	15
10000	10 000	2 0	1 0000	1 0	16
11111	11 111	3 7	1 1111	1 F	31
100000	100 000	4 0	10 0000	2 0	32
1100100	1 100 100	1 4 4	110 0100	6 4	100
11111111	11 111 111	3 7 7	1111 1111	F F	255

 

Operazioni aritmetiche

Tutte le notazioni posizionali utilizzano per le operazioni le stesse regole,

indipendentemente dalla base di rappresentazione adottata, quindi, le regole già note per la familiare rappresentazione in base 10 restano valide.

Esempi

 
 

Base 10	Base 2	Base16
15+	0000 1111 +	0F +
21=	0001 0101 =	15=
36	0010 0100	24

 

 
 

Base 10	Base 2	Base16
36-	0010 0100-	24 -
21=	0001 0101 =	15=
15	0000 1111	0F

 

Numeri interi senza segno in C ++

 
 

Tipo	Borland C++ 4.0   /16 bit	Borland C++ 4.0   /32 bit
unsigned short (int)	16 bit 0…216-1  da 0 a 65.535	16 bit 0…216-1  da 0 a 65.535
unsigned int	16 bit 0…216-1  da 0 a 65.535	32 bit 0…232-1  da 0 a 4.294.967.295
unsigned long (int)	32 bit 0…232-1  da 0 a 4.294.967.295	32 bit 0…232-1  da 0 a 4.294.967.295

 

Numeri interi

• una estensione dei numeri naturali (1,2,3...)
• che include anche lo zero
• e tutti i valori negativi della forma -N, essendo N un naturale

Numeri interi in un elaboratore: problematiche

• come rappresentare il "segno meno"
• possibilmente, rendere semplice l’esecuzione delle operazioni

Rappresentazione dei numeri interi

• rappresentazione in modulo e segno
• semplice e intuitiva
• ma inefficiente e complessa nella gestione delle operazioni ® non molto usata in pratica!

• rappresentazione in complemento a due
• meno intuitiva, costruita ad hoc
• rende semplice la gestione delle operazioni ® largamente usata!

• rappresentazione in codice eccesso 2^k-1
• meno intuitiva, costruita ad hoc
• usata per la rappresentazione della caratteristica dei reali

Rappresentazione in modulo e segno

Caratteristiche generali

• usa un bit (MSB Most Significant Bit) per rappresentare esplicitamente il segno

• usa poi gli altri bit disponibili per rappresentare il valore assoluto come numero binario puro

esempio:

8 bit (MSB = segno, bit 6...bit 0 = valore assoluto)

Note:

• segno completamente DISGIUNTO dal valore assoluto
• posizione del bit di segno entro la stringa di bit IRRILEVANTE (in linea di principio)

Difetti

• il valore 0 ha due distinte rappresentazioni (10000000 = "-0" e 00000000 = "+0")
• non permette di usare direttamente gli algoritmi già noti per eseguire le operazioni

-5 1 0000101

-- ---------------

0 1 0001010

e quindi:

• richiede circuiti specifici (o software più complesso) per la realizzazione dei sommatori
• maggior complicazione, maggior costo ® praticamente non molto utilizzata.

Rappresentazione in complemento a 2

Caratteristiche generali

• Rappresentazione non (completamente) posizionale

• il bit più significativo di una stringa di n bit ha peso -2^n-1 anziché 2^n-1 (gli altri bit mantengono il peso che è loro proprio, come in binario puro)

• il bit MSB (Most Significant Bit) rappresenta il segno (0 = +, 1 = -)

• permette di utilizzare direttamente gli algoritmi dei numeri naturali per eseguire le operazioni

In particolare verifica la proprietà X + (-X) = 0 usando le medesime regole dell'aritmetica binaria senza segno

esempio:

utilizzando n=8 bit, il bit 7 ha peso -128 anziché +128

quindi la stringa 11110001 denota il valore: -128 + 64 + 32 + 16 + 1 = -15

Valore denotato

Per definizione, il valore di un intero n espresso in questa notazione è dato dalla formula:

dove i d_k (k=0..n-1) sono le cifre binarie della rappresentazione del numero.

La formula differisce da quella usata per i numeri naturali solo per il peso negativo del MSB.

Come si ricava la rappresentazione in complemento a 2 di un numero?

Se il numero è positivo basta assegnare al bit del segno il valore 0 e codificare sui rimanenti k-1 bit il numero.

Se il numero è negativo basta rappresentare il suo complemento a 2 su k bit.

Per definizione si chiama complemento a 2 su k bit di un numero negativo quel valore che sommato al valore assoluto del numero da come risultato 2^k.

Cp₂ (-N) + |-N| = 2^k pertanto Cp₂ (-N) = 2^k - |-N|

Esempi

Con k= 8 e N= -5 la rappresentazione di –5 in complemento a 2 si ottiene rappresentando in binario su 8 bit il valore 251, infatti:

Cp₂ (-5) = 2^8-1 - |-N| = 256 – 5 = 251 ® 1111 1011

Con k= 8 e N= -1 la rappresentazione di –1 in complemento a 2 si ottiene rappresentando in binario su 8 bit il valore 255, infatti:

Cp₂ (-1) = 2^8-1 - |-1| = 256-1= 255 ® 1 1111111

Notazione in Complemento a due - Caratteristiche ed esempi

Conseguenze

MSB = 0 ® numero positivo (stesso valore che si avrebbe in binario puro: il diverso peso del MSB non ha influenza)

MSB = 1 ® numero negativo (il valore rappresentato si ottiene sommando il contributo negativo del MSB con i contributi positivi degli altri bit)

Esempi

la stringa 11110001 denota il valore -128 + 64 + 32 + 16 + 1,

cioè -15

la stringa 01110001 denota il valore 64 + 32 + 16 + 1,

cioè 113

la stringa 10000000 denota il valore -128 + 0,

cioè -128

la stringa 11111111 denota il valore -128+64+32+16+8+4+2+1,

cioè -1

la stringa 00000000 denota il valore 0,

cioè 0

la stringa 01111111 denota il valore 64+32+16+8+4+2+1,

cioè 127.

Osservazioni

valori opposti, come 15 e -15, hanno rappresentazioni completamente diverse

rappresentazioni identiche a meno del MSB denotano valori interi completamente diversi (non deve stupire: solo la rappresentazione in modulo e segno conserva le "somiglianze").

Notazione in Complemento a due - Proprietà

Range di valori rappresentabili

Nei due casi:

MSB=0 ® n-1 bit usabili come in binario puro ® range da 0 a 2^n-1-1

MSB=1 ® stesso intervallo traslato di -2 ^n-1 ® range da -2 ^n-1 a -1

Totale: range da -2 ^n-1 a 2 ^n-1-1

Esempio:

8 bit ® 256 combinazioni ® range -128…127 (anziché, come in binario puro, 0…255)

256 combinazioni allocate metà ai positivi e metà ai negativi, anziché tutte ai positivi

Osservazioni

• Il massimo intero positivo rappresentabile è di uno inferiore al minimo negativo rappresentabile perché lo 0 fa intrinsecamente parte dei positivi.

• Lo zero ha ora un’unica rappresentazione (efficienza, semplicità)

• Le somme algebriche si possono eseguire con le stesse regole dell’aritmetica binaria

• Tali regole rendono verificata la proprietà X + (-X) = 0 (con una piccola convenzione! trascurare il riporto)

• Non è necessario nessun circuito particolare per trattare i negativi ® semplicità e basso costo.

Notazione in Complemento a due – Esempi k=8

1) Operazione: -5 +3

Cp₂ (-5) = 2^8-1 - |-N| = 256 – 5 = 251 ® 1111 1011

La rappresentazione di +3 è nota (è identica a quella che si avrebbe in binario puro)

Cp₂ (-1) = 2^8-1 - |-1| = 256-1= 255 ® 1 1111111

Cp₂ (-5) = 2^8-1 - |-N| = 256 – 5 = 251 ® 1111 1011

operazione:

-1 11111111

-5 11111011

-- --------------

-6 (1)11111010

(e in effetti: 1 1111010 ® -128 + 122 = -6)

Il risultato va bene... a patto di ignorare il riporto!

3) Operazione: 3-(+5) 3+(-5)

La sottrazione: 3-(+5) considerando la cifra di prestito equivale alla somma 3+(-5)

3- (1)00000011 +3 00000011

5 00000101 -5 11111011

---- --------------- ---- ------------

-2 11111110 -2 11111110

Osservazioni

Il particolare sistema di rappresentazione produce relativamente alla somma e sottrazione risultati corretti in quanto:

• i valori positivi sono rappresentati come se la notazione fosse binaria pura

• i valori negativi hanno l’MSB che pesa -2^n-1 (-128) [anziché +2^n-1 (+128) come nel caso dei numeri naturali]

e sommando o sottraendo valori rappresentati in notazione complemento a due: per i negativi, si introduce un "errore" pari a 2n (infatti non si opera sul negativo -X, ma sul positivo 2n-X) che non influenza il risultato in quanto di fatto si lavora solo su n bit (o come si dice in modulo 2ⁿ ), quindi i riporti e prestiti oltre l’MSB, dovranno essere ignorati.

Notazione in Complemento a due - Algoritmo pratico di calcolo della rappresentazione in complemento a 2 di -X

La definizione formale di complemento a 2 è poco pratica per determinare la rappresentazione in complemento a due di un numero.

Una macchina ha bisogno di un procedimento semplice e facilmente meccanizzabile per determinare la rappresentazione in complemento a 2 di –X.

Poiché per definizione Cp₂ (-X) = 2ⁿ-X, osservando che:

• 2ⁿ-X si può anche scrivere come 2ⁿ-X -1+1

• l’operazione (2ⁿ-1) è una sottrazione solo in apparenza, perché (2ⁿ-1) è una sequenza di n bit pari a 1

• la differenza tra n uni e un numero binario X più piccolo (rappresentato con n bit) equivale a invertire tutti i bit della rappresentazione di X

• basta aggiungere 1

per ottenere 2ⁿ-X

Notazione in Complemento a due - Algoritmo pratico

1.determinare la rappresentazione binaria su n bit del positivo +X

2.invertire tutti i bit di tale rappresentazione

3.aggiungere 1 al risultato così ottenuto.

Esempio: determinazione della rappresentazione di -15 (su n=8 bit)

1) 15 ® 00001111

2) inversione ® 11110000

3) incremento di 1 ® 11110001 (verifica: -128 + 113 = -15)

Note

Il procedimento funziona anche al contrario.

Data la rappresentazione di -X, invertendo i bit e sommando 1 si ottiene la rappresentazione di X.

La notazione in complemento a due non va confusa con l’operazione di complementazione a due.

La notazione, definita formalmente come sopra, detta le regole per la rappresentazione di tutti i numeri interi (positivi e negativi).

L’effettuazione del calcolo del complemento a due, secondo l’algoritmo ora definito, serve invece a ottenere la rappresentazione del negativo -X a partire da quella del positivo X (e viceversa).

Notazione in Complemento a due - Errori nei calcoli

Cosa può succedere

-65 10111111 +65 01000001

-65 10111111 +65 01000001

---- ------------ ---- --------------

-130 (1)01111110 +130 10000010

Il risultato è sbagliato: la prima stringa denota +126, la seconda –126 e non–130 e +130 .

Il motivo è che con –130 e +130 siamo fuori dal range -128 ... 127.

Ciò deriva dal fatto che abbiamo sommato due valori che danno come risultato un valore esterno al range dei valori rappresentabili [-2^n-1... 2^n-1-1] e ciò ha provocato l’invasione da parte del risultato nel bit di segno ® OVERFLOW

Si ha overflow quando il numero di bit non è sufficiente per la rappresentazione del numero.

Non si ha overflow e quindi tutto funziona se

• l’MSB non è coinvolto in nessun riporto (né lo genera né lo riceve),
• oppure se lo è "totalmente" (ossia lo riceve ma lo rigenera anche).

Una regola pratica per vedere se il risultato è corretto, ovvero non si ha overflow, consiste nell’analizzare il segno dei numeri coinvolti nell’operazione di somma:

• operazioni tra numeri di segno diverso sono sempre corrette in quanto non si può uscire dal range
• operazioni tra numeri dello stesso segno sono corrette se il risultato mantiene il segno degli addendi.

Numeri interi in C ++

 
 

Tiposhort (int)	16 bit -216…216-1  -32768…32767		16 bit -216…216-1  -32768…32767
int	16 bit -216…216-1  -32768…32767		32 bit -232…232-1  -2.147.483.648 a 2.147.483.647
long (int)	32 bit -232…232-1  -2.147.483.648 a 2.147.483.647		32 bit -232…232-1  -2.147.483.648 a 2.147.483.647

 

Rappresentazione in codice eccesso 2^k-1

Caratteristiche generali

• Rappresentazione non (completamente) posizionale

• il bit MSB (Most Significant Bit) rappresenta il segno (0 = +, 1 = -)

Valore denotato

Per definizione, il valore di un intero n espresso in questa notazione è dato dalla formula:

dove i d_k (k=0..n-1) sono le cifre binarie della rappresentazione del numero.

La formula differisce da quella usata per i numeri naturali solo perché viene sottratto -2^n-1 .

esempio:

utilizzando n=8 bit, la stringa 11110001 (il bit 7 che ha peso +128 può essere ignorato dovendo altrimenti sottrarre 2⁷) denota il valore: 64 + 32 + 16 + 1 = 113

Nella rappresentazione polarizzata o come si dice in codice eccesso 2k-1, ove k è il numero di bit a disposizione, il numero N da rappresentare viene prima sommato ad una base prefissata pari a 2k-1, in modo che il valore risultante sia sempre positivo o nullo e poi codificato come se fosse un intero privo di segno.

Notazione in codice eccesso 2^k-1 - Proprietà

Range di valori rappresentabili

Nei due casi:

MSB=1 ® n-1 bit usabili come in binario puro ® range da 0 a 2^n-1-1

MSB=0 ® stesso intervallo traslato di -2 ^n-1 ® range da -2 ^n-1 a -1

Totale: range da -2 ^n-1 a 2 ^n-1-1

Esempio:

3 bit ® 8 combinazioni ® range -4…3 (anziché, come in binario puro, 0…7)

8 combinazioni allocate metà ai positivi e metà ai negativi, anziché tutte ai positivi

N N+2^3-1

3 ( 3+4) 111

2 ( 2+4) 110

1 ( 1+4) 101

0 ( 0+4) 100

-1 (-1+4) 011

-2 (-2+4) 010

-3 (-3+4) 001

-4 (-4+4) 000

Anche con questo tipo di rappresentazione il primo bit rappresenta il segno, ma a differenza dei sistemi precedenti i numeri negativi hanno il bit del segno a 0 ed i positivi, incluso lo zero hanno il bit del segno a 1.

Vantaggi

I numeri negativi e positivi sono ordinati in ordine crescente

Come si ricava la rappresentazione in codice eccesso 2^k-1 di un numero?

Se il numero è positivo basta assegnare al bit del segno il valore 1 e codificare sui rimanenti k-1 bit il numero.

Se il numero è negativo basta sommare al numero negativo 2^k-1 e rappresentare il risultato in binario puro su k bit.

Come si ricava il valore di un numero data la sua rappresentazione in codice eccesso 2^k-1?

Data la rappresentazione di N in codice eccesso 2k-1, per trovare il valore di N si guarda il bit MSB:

• se vale 1, si tratta di un numero positivo, basta calcolare il valore che corrisponde alla stringa binaria ignorando il contributo della cifra di posto k-1,
• se invece vale 0, si tratta di un numero negativo, dopo aver calcolato il valore che corrisponde alla stringa binaria devo sottrarre 2k-1.

Ad esempio per k=3

• la sequenza 101 rappresenta il numero positivo 101® 01® +1,
• mentre la sequenza 001 rappresenta il numero negativo 1- 23-1® -3.

Osservazioni

Si noti che a causa delle dimensioni limitate della memoria nell'aritmetica intera non valgono la proprietà associativa e commutativa della somma e del prodotto e la proprietà distributiva della somma.

Infatti per esempio se A è il massimo intero rappresentabile, l'espressione (A-A)+A (che calcolata dà il risultato corretto pari ad A) non equivale a A-(A+A), in quanto il risultato parziale (A+A) non è rappresentabile.