Abilità Informatiche e Telematiche
(Laurea Triennale + Laurea Magistrale)
Marco Pedicini
mailto:marco.pedicini@uniroma3.it
Corso di Laurea in Scienze della Comunicazione, Università Roma Tre
12 Dicembre 2012 - 11 Gennaio 2013
Parte XIII
UD 5.1 – La rappresentazione
dell’informazione
Alla fine di questa UD sarai in grado di
• Sapere come l’informazione viene memorizzata in un calcolatore
• Conoscere i sistemi di numerazione posizionali ed in particolare il sistema di numerazione in base dieci e il sistema di numerazione in base due
• Effettuare operazioni in binario
• Saper convertire un numero dalla base due alla base dieci e viceversa
Contenuti
• Vincoli per la rappresentazione dell’informazione all’interno di un calcolatore
• bit e byte
• Strategie per la codifica dei dati
• Sistemi di numerazione posizionale
• Base dieci
• Base due
• Operazioni in algebra binaria
• Conversione di un numero
• Conversione dal sistema decimale al binario
• Conversione dal sistema binario al sistema decimale
La codifica dei dati
Informatica
L’informatica è la scienza che si occupa della rappresentazione e della elaborazione dell’informazione.
L’informazione non va erroneamente vista come qualcosa di statico, ma va dunque considerata come la combinazione tra
• dati: rappresentazione delle entità di interesse,
• interpretazione: regole per la trasformazione dei dati (descrizione del problema) in altri dati (soluzione del problema), regole per l’intellegibilità dei dati (associazione dei dati ad entità semantiche).
Rappresentazione dell’informazione
Dobbiamo considerare due aspetti:
• supporto fisico: l’informazione deve essere scritta/trasportata utilizzando un supporto fisico (ad esempio: la carta, un disco, un circuito);
• codifica: la trasformazione dell’informazione in dato in modo che ne sia possibile la gestione tramite il supporto fisico, corrisponde alla creazione di un linguaggio (ad esempio: la lingua italiana, un sistema di numerazione) e ne costituisce il supporto logico.
Linguaggio di codifica
Un linguaggio è tipicamente costituito da
• un insieme finito di simboli dettoalfabetoe da
• un insieme di regole che permettono di combinare tali simboli dettagrammatica.
Gli aspetti quantitativi nella codifica dell’informazione sono oggetto di studio nellaTeoria dell’Informazione(disciplina fondata dal lavoro di Claude Shannon nel 1948), ma è subito chiaro che da un punto di vista quantitativo vi è una maggiore efficienza nel considerare alfabeti con almeno due simboli.
Sistemi automatici
• Per poter elaborare automaticamente informazione, è necessario darne una rappresentazione che sia gestibile da uno strumento automatico
• Esistono fonti di informazione estremamente diverse per il loro trattamento automatico tramite un determinato
supporto fisico è necessaria un’adeguata e uniforme modalità di rappresentazione;
• nel caso dei calcolatori tutta l’informazione viene
mantenuta in forma numerica, con il più semplice sistema di numerazione possibile, quello binario (con due soli simboli);
• inoltre anche gli altri dati sono codificati in forma numerica, tramite numeri interi finiti.
L’informazione all’interno del calcolatore
• La possibilità di rappresentare informazione in un calcolatore è condizionata da due vincoli:
1 il calcolatore gestiscesolo sequenze di bit
• condizione dettata dal fatto che i dispositivi elettronici possono facilmente rappresentare le due cifre 0 e 1 (associandola al passaggio di un flusso elettrico) 2 il calcolatore ha unamemoria limitata
• ne segue che la quantità di memoria dedicata alla
rappresentazione di una singola informazione è anch’essa limitata
• Questi due vincoli sono largamente indipendenti tra loro
• anche se il calcolatore avesse una memoria infinita dovremmo comunque studiare il modo di rappresentare i dati in binario
• anche se il calcolatore potesse memorizzare direttamente informazioni generiche (per esempio numeri decimali) avremmo comunque il problema della limitatezza della sua memoria
Codifica numerica dei dati
• Dal punto di vista della rappresentazione, un dato può essere di vari tipi:
• categorico: rosso, verde, blu
• ordinale: orrendo, brutto, bello, fantastico
• numeralediscreto: 10, 159, -10
• numeralecontinuo: 1e − 13 = 1 1013,√
2.
• Tutti questi tipi possono essere rappresentati o approssimati tramite numeri interi (possibilmente esprimendo una parte frazionaria, la virgola)
Codifica dei dati – il bit
• In un calcolatore i dati e le istruzioni di un programma sono codificati in forma binaria, ovvero come sequenze finite di cifre 0 e 1
• il bit è la forma elementare (atomica) di dato memorizzabile in un calcolatore
• un bit può avere valore 0 oppure 1
• la parola ’bit’ è una forma contratta per binary digit (cifra binaria)
• ciascun bit è memorizzato in una cella elementare di memoria, fisicamente realizzata come dispositivo elettronico bistabile (in cui sono chiaramente distinguibili due stati)
• questi due stati vengono fatti corrispondere allo 0 e all’1
• Un bit è quindi un dato che può essere utilizzato soltanto per rappresentare una informazione binaria
• Per rappresentare altre tipologie di informazioni sono necessarie sequenze di bit
Codifica dei dati – il byte
• Il byte è la più piccola sequenza di bit
• un byte è una sequenza di 8 bit
• Le possibili combinazioni degli 8 bit in un byte sono 28=256
• un byte può essere utilizzato per rappresentare un valore tra 256 diversi possibili valori
• ad esempio, un piccolo numero intero, un carattere in un alfabeto che contiene non più di 256 caratteri, ...
• in generale, sono possibili diverse scelte sull’insieme dei valori possibili
• ad esempio, con un byte si può rappresentare un numero naturale compreso nell’intervallo da 0 a 255, oppure un numero intero relativo nell’intervallo da -128 a +127
• Per rappresentare altre tipologie di informazioni sono necessarie sequenze di bit più grandi
Strategie per la codifica dei dati
Nel codificare una informazione in un dato binario possiamo usare due diverse strategie
• codifica tabellare(metodo del dizionario)
• applicabile quando l’insieme dei valori che può assumere l’informazione è finito
• si fa corrispondere ad ogni valore dell’informazione una diversa combinazione di 0 e di 1
• conversione di base
• applicabile quando l’informazione è già rappresentata sotto forma di numero (eventualmente rappresentato in base 10)
• si premette una fase di traduzione in cui il numero viene convertito in base 2
L’aritmetica binaria con memoria illimitata
Sistema di numerazione posizionale
• i numeri naturali sono di solito rappresentati tramite un sistema di numerazione posizionale
• i simboli utilizzati nella rappresentazione del numero hanno un peso dipendente dalla loro posizione all’interno della stringa
• il sistema di numerazione abituale utilizza la base dieci (detto anche decimale)
• la numerazione in base dieci fa uso di dieci simboli (cifre):
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
• un numero è denotato da una sequenza di cifre
• il valore di una cifra dipende dalla cifra stessa e dalla sua posizione nella sequenza
• per esempio la sequenza di cifre 563 corrisponde al numero 5 × 100 + 6 × 10 + 3 = 563
Sistema di numerazione in base dieci
• La sequenza di cifre
563
• Rappresenta il numero
5 × 100 + 6 × 10 + 3 × 1 = 500 + 60 + 3 = 563
• la cifra 5 pesa di più della cifra 6 perché si trova in una posizione più a sinistra (più significativa)
Base generica b
• Il sistema di numerazione posizionale può essere
generalizzato a qualsiasi base b, disponendo di b simboli diversi la sequenza di cifre
XYZ
• rappresenta il numero
X × b2+Y × b1+Z × b0
Esempi di basi di uso frequente
• Sistema di numerazione in base dieci (o decimale)
• utilizza i simboli
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
• adottato per gli ovvi rapporti con la rappresentazione tramite flessione delle dita
• Sistema di numerazione in base due (o binario)
• utilizza i simboli 0 e 1
• adottato dai calcolatori elettronici per la facilità di
rappresentare mediante grandezze elettromagnetiche due stati, corrispondenti ai due simboli 0 e 1
• Sistema di numerazione in base sedici (o esadecimale)
• utilizza i simboli
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E , F
• adottato per la sua compattezza e per la facilità di conversione con la rappresentazione binaria
• Sistema di numerazione in base uno (o unario)
• utilizza solo il simbolo I
• non è veramente un sistema posizionale
• adottato talvolta perché il numero può essere incrementato facilmente con l’aggiunta di una cifra (esempio: III + I = IIII )
Esempi di basi di uso frequente
• Sistema di numerazione in base dieci (o decimale)
• utilizza i simboli
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
• adottato per gli ovvi rapporti con la rappresentazione tramite flessione delle dita
• Sistema di numerazione in base due (o binario)
• utilizza i simboli 0 e 1
• adottato dai calcolatori elettronici per la facilità di
rappresentare mediante grandezze elettromagnetiche due stati, corrispondenti ai due simboli 0 e 1
• Sistema di numerazione in base sedici (o esadecimale)
• utilizza i simboli
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E , F
• adottato per la sua compattezza e per la facilità di conversione con la rappresentazione binaria
• Sistema di numerazione in base uno (o unario)
• utilizza solo il simbolo I
• non è veramente un sistema posizionale
• adottato talvolta perché il numero può essere incrementato facilmente con l’aggiunta di una cifra (esempio: III + I = IIII )
Esempi di basi di uso frequente
• Sistema di numerazione in base dieci (o decimale)
• utilizza i simboli
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
• adottato per gli ovvi rapporti con la rappresentazione tramite flessione delle dita
• Sistema di numerazione in base due (o binario)
• utilizza i simboli 0 e 1
• adottato dai calcolatori elettronici per la facilità di
rappresentare mediante grandezze elettromagnetiche due stati, corrispondenti ai due simboli 0 e 1
• Sistema di numerazione in base sedici (o esadecimale)
• utilizza i simboli
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E , F
• adottato per la sua compattezza e per la facilità di conversione con la rappresentazione binaria
• Sistema di numerazione in base uno (o unario)
• utilizza solo il simbolo I
• non è veramente un sistema posizionale
• adottato talvolta perché il numero può essere incrementato facilmente con l’aggiunta di una cifra (esempio: III + I = IIII )
Esempi di basi di uso frequente
• Sistema di numerazione in base dieci (o decimale)
• utilizza i simboli
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
• adottato per gli ovvi rapporti con la rappresentazione tramite flessione delle dita
• Sistema di numerazione in base due (o binario)
• utilizza i simboli 0 e 1
• adottato dai calcolatori elettronici per la facilità di
rappresentare mediante grandezze elettromagnetiche due stati, corrispondenti ai due simboli 0 e 1
• Sistema di numerazione in base sedici (o esadecimale)
• utilizza i simboli
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E , F
• adottato per la sua compattezza e per la facilità di conversione con la rappresentazione binaria
• Sistema di numerazione in base uno (o unario)
• utilizza solo il simbolo I
• non è veramente un sistema posizionale
• adottato talvolta perché il numero può essere incrementato facilmente con l’aggiunta di una cifra (esempio: III + I = IIII )
Sistema di numerazione in base due
• Il sistema di numerazione in base due (detto anche binario) fa uso dei due soli simboli 0 e 1
• dunque una sequenza di bit XYZ
• rappresenta il numero
X × 22+Y × 21+Z × 20
Sistema di numerazione in base due
• Il sistema di numerazione in base due (detto anche binario) fa uso dei due soli simboli 0 e 1
• dunque una sequenza di bit XYZ
• rappresenta il numero
X × 22+Y × 21+Z × 20
Aritmetica in binario
• L’aritmetica con i numeri binari è analoga a quella in base 10, gli algoritmi per le quattro operazioni quasi coincidono con quelli utilizzati nell’aritmetica in base 10.
• Consideriamo per iniziare l’addizione:
La tabella di base per eseguire l’addizione ad una cifra è la seguente:
0 + 0 = 0 0 + 1 = 1 1 + 0 = 1
1 + 1 = 0 con riporto di 1
bisogna solo ricordare che
1 + 1 = 10
e quindi quando si sommano due 1 il risultato sarà 0 con il riporto di 1.
Esempio di addizione
Tabella Addizione
0 + 0 =0
0 + 1 =1
1 + 0 =1
1 + 1 = 0 con riporto di 1
• Primo Caso: 3 + 1 = 4
1 1 + 0 1 = 1 0 0
• Secondo Caso: 23 + 30 = 53
1 0 1 1 1 + 1 1 1 1 0 = 1 1 0 1 0 1
Operazioni con i numeri binari
• Esempio di sottrazione di interi
• lo sappiamo fare solo se il primo numero (minuendo) è maggiore del secondo numero (sottraendo)
La tabella di base per eseguire la sottrazione ad una cifra è la seguente:
0 − 0 = 0 1 − 1 = 0 1 − 0 = 1
0 - 1 = 1 con riporto negativo di 1 il riporto negativo è il prestito di un uno dalla cifra successiva, dunque bisogna solo ricordare che
10 − 1 = 1
e quindi quando si sottrae 1 da zero è necessario considerare un riporto negativo di 1 sulla cifra seguente.
Esempio di sottrazione
Tabella Sottrazione
0 − 0 =0
1 − 1 =0
1 − 0 =1
0 - 1 = 1 con riporto negativo di 1
• Primo Caso: 9 − 2 = 7
1 0 0 1 − 1 0 = 1 1 1
• Secondo Caso: 30 − 23 = 7
1 1 1 1 0 − 1 0 1 1 1 = 0 0 1 1 1
Operazioni con i numeri binari
• Algoritmo per il prodotto di interi
• la moltiplicazione si fa utilizzando esattamente utilizzando l’algoritmo per la moltiplicazione in decimale, la differenza emerge solo al momento della somma per cui si utilizza l’algoritmo della somma in binario.
La tabella di base per eseguire la moltiplicazione ad una cifra è la seguente (identica a quella in base 10):
0 · 0 = 0 0 · 1 = 0 1 · 0 = 0 1 · 1 = 1
• Quando si moltiplica il moltiplicando per una cifra del moltiplicatore
• se la cifra è 0 si annulleranno tutte le cifre e vi sarà l’addendo corrispondente uguale a 0
• se la cifra è 1 il moltiplicando sarà copiato come addendo a partire dalla posizione della cifra del moltiplicatore
Operazioni con i numeri binari
Tabella Moltiplicazione
0 · 0 =0
0 · 1 =0
1 · 0 =0
1 · 1 =1
Esempio di moltiplicazione di interi
1 0 1 1 0 × moltiplicando 1 0 1 = moltiplicatore
1 0 1 1 0 addendo 1a cifra
0 0 0 0 0 addendo 2a cifra
1 0 1 1 0 addendo 3a cifra
1 1 0 1 1 1 0 risultato
Operazioni con i numeri binari
Moltiplicare un numero binario per 2k equivale a traslare a sinistra tutte le cifre di k posizioni
1 0 1 1 0 ×
1 0 0 =
0 0 0 0 0
0 0 0 0 0
1 0 1 1 0
1 0 1 1 0 0 0
Operazioni con i numeri binari
Esempio di divisione tra interi, si procede per sottrazioni successive
1 0 1 1 0
1 0 1 1
0 0 1 0
1 0 1 0
0 0 1 0
1 0 1 0
1 0
Dunque il risultato si legge sulla colonna di destra ed è 100 il resto invece è ciò che troviamo in fondo alla successione di sottrazioni e in questo caso è 10.
Operazioni con i numeri binari
Dividere per 2k un numero in binario equivale a traslare tutte le cifre a destra di k posizioni (analogamente alla divisione per una potenza di 10 nel caso di un numero rappresentato in base 10).
Le conversioni di base
Schema generale
Nella conversione di un numero nella rappresentazione in base x ad una rappresentazione in base y , si possono presentare i seguenti casi:
1 Si conosce l’aritmetica nella base x ma NON si conosce l’aritmetica nella base y (Caso 1)
2 Si conosce l’aritmetica della base y ma NON si conosce l’aritmetica della base x (Caso 2)
3 NON si conosce l’aritmetica nella base y , NON si conosce l’aritmetica nella base x (Caso 3)
Regole di Conversione
Nei tre casi si applicano le seguenti regole:
1 Si applica la regola delle divisioni successive
• Es.: Base 10 => Base 2 (caso 1)
2 Si applica la regola dei pesi
• Es: Base 2 => Base 10 (caso 2)
3 Si passa per una base intermedia Z di cui si conosce l’aritmetica
• Es.: Base 5 => Base 9 (passiamo per la base 10) (caso 3)
Conversione di un decimale in un binario
La regola delle divisioni successive si itera la divisione del numero per la base (2) e si prende nota ad ogni iterazione del resto della divisione:
quoziente resto
75 1
37
1
18 0
9 1
4 0
2 0
1 1
0
Dunque il risultato si rilegge dalla colonna dei resti partendo dal basso: 1001011.
Conversione di un decimale in un binario
La regola delle divisioni successive si itera la divisione del numero per la base (2) e si prende nota ad ogni iterazione del resto della divisione:
quoziente resto
75 1
37 1
18
0
9 1
4 0
2 0
1 1
0
Dunque il risultato si rilegge dalla colonna dei resti partendo dal basso: 1001011.
Conversione di un decimale in un binario
La regola delle divisioni successive si itera la divisione del numero per la base (2) e si prende nota ad ogni iterazione del resto della divisione:
quoziente resto
75 1
37 1
18 0
9
1
4 0
2 0
1 1
0
Dunque il risultato si rilegge dalla colonna dei resti partendo dal basso: 1001011.
Conversione di un decimale in un binario
La regola delle divisioni successive si itera la divisione del numero per la base (2) e si prende nota ad ogni iterazione del resto della divisione:
quoziente resto
75 1
37 1
18 0
9 1
4
0
2 0
1 1
0
Dunque il risultato si rilegge dalla colonna dei resti partendo dal basso: 1001011.
Conversione di un decimale in un binario
La regola delle divisioni successive si itera la divisione del numero per la base (2) e si prende nota ad ogni iterazione del resto della divisione:
quoziente resto
75 1
37 1
18 0
9 1
4 0
2
0
1 1
0
Dunque il risultato si rilegge dalla colonna dei resti partendo dal basso: 1001011.
Conversione di un decimale in un binario
La regola delle divisioni successive si itera la divisione del numero per la base (2) e si prende nota ad ogni iterazione del resto della divisione:
quoziente resto
75 1
37 1
18 0
9 1
4 0
2 0
1 1
0
Dunque il risultato si rilegge dalla colonna dei resti partendo dal basso: 1001011.
Conversione da un binario ad un decimale
La regola dei pesi viene dalla definizione stessa di sistema di numerazione posizionale: il valore rappresentato da una parola scritta in base 2 si ottiene sommando le potenze successive della base moltiplicate per la cifra nella posizione
corrispondente.
Esempio: il numero 10011 in base due si converte nel numero 1 × 24+0 × 23+0 × 22+1 × 21+1 × 20=16 + 2 + 1 = 19
Conversione tra basi qualunque
Non conoscendo né l’aritmetica della base di partenza e né quella della base di arrivo, si procede passando per una base intermedia.
Cosa abbiamo studiato
Vincoli per la rappresentazione dell’informazione nella memoria di un calcolatore
• bit e byte
• introduzione alle strategie per la codifica dei dati
• i sistemi di numerazione posizionale, con particolare attenzione al sistema di numerazione in base dieci e al sistema di numerazione in base due
• le operazioni in binario
• le regole dei cambiamenti di base
• la rappresentazione degli interi positivi
Parte XIV
UD 5.2 – Rappresentazione di
ulteriori dati numerici
Alla fine di questa UD sarai in grado di
• Scrivere la rappresentazione binaria di numeri interi relativi in algebra modulare modulo k :
• In modulo e segno
• In complemento a uno
• In complemento a due
• Svolgere operazioni in complemento a due
• Comprendere la circolarità della rappresentazione
• Saper rappresentare un numero razionale
La rappresentazione degli interi relativi
Rappresentazione di interi relativi
• Nella rappresentazione dei numeri interi relativi occorre destinare alcune combinazioni di bit alla rappresentazione dei numeri negativi oltre che alla rappresentazione dei numeri positivi:
• Il sistema intuitivo è quello di rappresentare esplicitamente il segno ed il modulo
• questa rappresentazione è chiamata modulo e segno
• Il sistema più utilizzato è però quello di usare il complemento alla base
• nel caso binario si dice “rappresentazione in complemento a due”
Rappresentazione modulo e segno
Questa rappresentazione è di facile lettura, ma è difficile eseguire operazioni aritmetiche, perché il segno va trattato in maniera difforme dagli altri bit ed inoltre si hanno due zeri: zero positivo e zero negativo.
• Attenzione ! La parola modulo qui ha il significato di valore assoluto ovvero numero senza segno, ad esempio il modulo (valore assoluto) di -3 è |-3|=3.
• Il primo bit della sequenza rappresenta il segno, gli altri il modulo
• se il primo bit vale 0 allora il numero è positivo, altrimenti se vale 1 il numero rappresentato è negativo
• esempio con sequenze di quattro bit:
0000 +0 1000 -0 0001 +1 1001 -1 0010 +2 1010 -2 0011 +3 1011 -3 0100 +4 1100 -4 0101 +5 1101 -5 0110 +6 1110 -6 0111 +7 1111 -7
Operazione di complementazione
• Introduciamo, per la comprensione del prosieguo, una definizione fondamentale.
• Data una sequenza di k cifre che rappresenta il numero N in base b, si definisce:
• complemento alla base del numero N il valore Cb=bk − N
• complemento diminuito del numero N il valore Cd =Cb− 1
• Da cui si ricava che il complemento alla base si ottiene sommando 1 al complemento diminuito:
Cb=Cd+1
Operazione di complementazione
Nel sistema binario, il complemento alla base Cbprende il nome dicomplemento a due, mentre il complemento diminuito Cd viene dettocomplemento a uno.
• Regola pratica di calcolo: nel sistema binario, il
complemento a uno di un numero si ottiene semplicemente sostituendo nella sequenza di bit
• 0 con 1 e
• 1 con 0
• Nota bene che per qualsiasi base valgono le seguenti proprietà
Cb(Cb(N )) = bk − (bk − N ) = N
Cd(Cd(N )) = bk−(bk−N −1)−1 = bk−bk+N +1−1 = N ovvero che ilcomplemento del complemento di N è uguale a N
Operazione di complementazione
Esempi:
• N = 001(2)
• Cd =110(2) complemento a uno
• Cb=110(2)+1 = 111(2) complemento a due
• N = 100(2)
• Cd =011(2) complemento a uno
• Cb=011(2)+1 = 100(2) complemento a due
• N = 000(2)
• Cd =111(2) complemento a uno
• Cb=111(2)+1 = 000(2) complemento a due
Rappresentazione in complemento a uno
• Data una sequenza di cifre che rappresenta ilmodulo (valore assoluto) dell’intero relativo che si vuole rappresentare in complemento a uno, si ottiene la
sequenza che rappresenta il numero in funzione del segno del numero secondo le seguenti regole:
• positivi: usando la rappresentazione binaria del modulo
• negativi: complementando ad uno l’intera sequenza binaria della rappresentazione binaria del modulo
Complemento ad uno
• Gli intervalli rappresentati sono simmetrici ma con doppia rappresentazione dello zero:
• lo zero si rappresenta sia come 00000 che come 11111.
• le sequenze di bit che iniziano per 0 rappresentano gli interi positivi
• le sequenze che iniziano per 1 rappresentano gli interi negativi.
• Esempi:
• caso degli interi positiviconversione di +232 nella rappresentazione in complemento a uno di lunghezza 10:
ottenere la rappresentazione in binario di 232 utilizzando il metodo delle divisioni successive,
232 → 0011101000
• caso degli interi negativiconversione di -232 nella rappresentazione in complemento a uno: ottenere la rappresentazione in binario di 232 utilizzando il metodo delle divisioni successive, e complementare ogni cifra:
232 → 0011101000 − 232 → 1100010111
Esempi di complemento ad uno a k = 5 cifre
Assoluto Positivo Negativo
5 → 00101(2) +5 → 00101(2) −5 → 11010(2) 11 → 01011(2) +11 → 01011(2) −11 → 10100(2) 0 → 00000(2) +0 → 00000(2) −0 → 11111(2)
Rappresentazione in complemento a due
Nella rappresentazione in complemento a due utilizziamo la proprietà
Cb(N ) = Cd(N ) + 1
quindi i numeri negativi si ottengono dai corrispondenti numeri positivi complementando ad 1 ogni cifra e sommando uno La prima cifra continua sempre a rappresentare il segno ed inoltre si ha un solo zero
Rappresentazione in complemento a due
Regola pratica per ottenere la rappresentazione di un numero negativo da quella del corrispondente positivo:
partendo da destra si lasciano invariate tutte le cifre fino al primo uno (incluso) e poi si invertono tutti i successivi.
Esempi di somme in complemento a due
2 + 3 = 5 0 0 1 0 riporti 0 0 1 0 + 0 0 1 1 = 0 1 0 1 2 + 3 = 5 1 1 0 0 riporti 1 1 1 0 + 1 1 0 1 = 1 0 1 1 -2 + -3 = -5 (-2) + (-3) = -5
Esempi di operazioni in complemento a due
2 + (-3) = -1 0 0 0 0 riporti 0 0 1 0 + 1 1 0 1 = 1 1 1 1 2 + -3 = -1 Sottrazione: 3 - 2 = 3 + (-2) = 1 1 1 1 0 riporti 0 0 1 1 + 1 1 1 0 = 0 0 0 1 3 + -2 = 1
Overflow e underflow
Overflow: 2 + 6 = -8 0 1 1 0 riporti 0 0 1 0 + 0 1 1 0 = 1 0 0 0 2 + 6 = -8 Underflow: (-2) + (-7) = 7 1 0 0 0 riporti 1 1 1 0 + 1 0 0 1
= 0 1 1 1 -2 + -7 = 7
Circolarità della rappresentazione
0000 0001 0010 0011 0100 0111 0110 0101 1000 1100 1101 1111 1110 1001 1011 1010 0 1 2 3 4 5 6 7 - 8 -7 -6 -5 -4 -3 -2 -1 +1 -1
Aritmetica con il complemento a due
• La somma di due numeri relativi di n cifre si esegue come nel caso dei numeri naturali
• l’eventuale riporto sulla cifra n+1 viene ignorato
• se il risultato eccede 2n− 1 1 si ottiene un numero negativo che non corrisponde al risultato desiderato
• se il risultato è minore di −2n− 1 si ottiene un numero positivo che non corrisponde al risultato desiderato
• la sottrazione tra due numeri relativi di n cifre si esegue complementando a due il secondo numero ed eseguendo la somma.
Domande
• Supponi che la piattaforma ’Kimbo’ consenta di
rappresentare i numeri interi relativi in complemento a due tramite uno dei seguenti formati
• formato ’byte’: 8 bit
• formato ’short’: 16 bit
• formato ’int’: 32 bit
• formato ’long’: 64 bit
• Quali numeri è possibile rappresentare con ognuno di questi formati ?
Risposte
• Con 8 bit è possibile rappresentare in complemento a due i numeri da −27a 27− 1
• l’intervallo, dunque, è [−128, +127]
• Con 16 bit è possibile rappresentare in complemento a due i numeri da −215a 215− 1
• 215=25× 210=32 × 1024 ovvero circa 32 × 1000 = 32.000
• l’intervallo è infatti [−32.768, +32.767]
• Con 32 bit è possibile rappresentare in complemento a due i numeri da −231a 231− 1
• 231=2 × 210× 210× 210=2 × 1024 × 1024 × 1024
• ovvero circa 2 × 1000 × 1000 × 1000 = 2.000.000.000
• l’intervallo è infatti [−2.147.483.648, +2.147.483.647]
• Con 64 bit è possibile rappresentare in complemento a due i numeri da −263a 263− 1
• 263=23× 210× 210× 210× 210× 210× 210
• ovvero circa 2 × 1018
• l’intervallo è
[09.223.372.036.854.775.808, +9.223.372.036.854.775.807]
Risposte
• Con 8 bit è possibile rappresentare in complemento a due i numeri da −27a 27− 1
• l’intervallo, dunque, è [−128, +127]
• Con 16 bit è possibile rappresentare in complemento a due i numeri da −215a 215− 1
• 215=25× 210=32 × 1024 ovvero circa 32 × 1000 = 32.000
• l’intervallo è infatti [−32.768, +32.767]
• Con 32 bit è possibile rappresentare in complemento a due i numeri da −231a 231− 1
• 231=2 × 210× 210× 210=2 × 1024 × 1024 × 1024
• ovvero circa 2 × 1000 × 1000 × 1000 = 2.000.000.000
• l’intervallo è infatti [−2.147.483.648, +2.147.483.647]
• Con 64 bit è possibile rappresentare in complemento a due i numeri da −263a 263− 1
• 263=23× 210× 210× 210× 210× 210× 210
• ovvero circa 2 × 1018
• l’intervallo è
[09.223.372.036.854.775.808, +9.223.372.036.854.775.807]
Risposte
• Con 8 bit è possibile rappresentare in complemento a due i numeri da −27a 27− 1
• l’intervallo, dunque, è [−128, +127]
• Con 16 bit è possibile rappresentare in complemento a due i numeri da −215a 215− 1
• 215=25× 210=32 × 1024 ovvero circa 32 × 1000 = 32.000
• l’intervallo è infatti [−32.768, +32.767]
• Con 32 bit è possibile rappresentare in complemento a due i numeri da −231a 231− 1
• 231=2 × 210× 210× 210=2 × 1024 × 1024 × 1024
• ovvero circa 2 × 1000 × 1000 × 1000 = 2.000.000.000
• l’intervallo è infatti [−2.147.483.648, +2.147.483.647]
• Con 64 bit è possibile rappresentare in complemento a due i numeri da −263a 263− 1
• 263=23× 210× 210× 210× 210× 210× 210
• ovvero circa 2 × 1018
• l’intervallo è
[09.223.372.036.854.775.808, +9.223.372.036.854.775.807]
Risposte
• Con 8 bit è possibile rappresentare in complemento a due i numeri da −27a 27− 1
• l’intervallo, dunque, è [−128, +127]
• Con 16 bit è possibile rappresentare in complemento a due i numeri da −215a 215− 1
• 215=25× 210=32 × 1024 ovvero circa 32 × 1000 = 32.000
• l’intervallo è infatti [−32.768, +32.767]
• Con 32 bit è possibile rappresentare in complemento a due i numeri da −231a 231− 1
• 231=2 × 210× 210× 210=2 × 1024 × 1024 × 1024
• ovvero circa 2 × 1000 × 1000 × 1000 = 2.000.000.000
• l’intervallo è infatti [−2.147.483.648, +2.147.483.647]
• Con 64 bit è possibile rappresentare in complemento a due i numeri da −263a 263− 1
• 263=23× 210× 210× 210× 210× 210× 210
• ovvero circa 2 × 1018
• l’intervallo è
[09.223.372.036.854.775.808, +9.223.372.036.854.775.807]
La rappresentazione dei numeri razionali
Rappresentazione di numeri razionali
• La difficoltà della rappresentazione dei numeri razionali deriva dal fatto che un intervallo arbitrariamente piccolo ne contiene infiniti
• E’ dunque possibile rappresentarne solo un sottoinsieme
• Una delle rappresentazioni più utilizzate è quella in virgola mobile, anche detta floating point
Rappresentazione in virgola mobile
Un qualunque numero razionale può essere riscritto in modo da evidenziare unamantissaed unesponente
• Esempi:
• 235.023 = .235023 × 103(.235023 è la mantissa, 3 è l’esponente)
• −0.0000235 = −.235 × 10 − 4 (−.235 è la mantissa, −4 è l’esponente)
• Ciò è vero anche per i numeri in base due, ad esempio:
• m = 1001001.0101 = .10010010101 × 2−7(10010010101 mantissa e −7 esponente)
• La rappresentazione in virgola mobile consiste proprio nel rappresentare mantissa ed esponente del numero
razionale espresso in base due
• un bit viene generalmente usato per il segno della mantissa m
• una porzione dei bit viene dedicata alla rappresentazione della mantissa
• i rimanenti bit vengono utilizzati per rappresentare l’esponente in complemento a due
Cosa abbiamo studiato
Vincoli per la rappresentazione dell’informazione nella memoria di un calcolatore
• bit e byte
• introduzione alle strategie per la codifica dei dati
• i sistemi di numerazione posizionale, con particolare attenzione al sistema di numerazione in base dieci e al sistema di numerazione in base due
• le operazioni in binario
• le regole dei cambiamenti di base
• la rappresentazione degli interi positivi
• modulo e segno
• complemento a uno
• complemento a due
• le operazioni in complemento a due
• la circolarità della rappresentazione
• la rappresentazione dei numeri razionali