Sistemi di Numerazione Binaria

Fondamenti di Informatica - Prof. Gregorio Cosentino12/02/2011 1

Numeri e numerali

•Numero: entità astratta•Numerale : stringa di caratteri che rappresenta un numero in un dato sistema di numerazione

• Lo stesso numero è rappresentato da numerali diversi in diversi sistemi

ES– 156 nel sistema decimale– CLVI in numeri romani

• Il numero di caratteri nel numerale determina l’intervallo di numeri rappresentabili

ES– interi a 3 cifre con segno in notazione decimale: [-999,+999]

Fondamenti di Informatica - Prof. Gregorio Cosentino12/02/2011 2

Numeri a precisione finita

• Numero finito di cifre • Si perdono alcune proprietà:

– chiusura operatori ( +, -, x )– prop. associativa, distributiva,..

ES– 2 cifre decimali e segno [-99,+99]– 78+36=114 (Chiusura)– 60+(50-40) ≠ (60+50)-40 (Associatività)

• Errori di arrotondamento• Buchi nella rappresentazione dei realiES

– usando numerali decimali con duesole cifre frazionarie:

0?

0.01 0.02Fondamenti di Informatica - Prof. Gregorio Cosentino12/02/2011 3

GC1

Sistemi posizionali

Fondamenti di Informatica - Prof. Gregorio Cosentino12/02/2011 4

•Il sistema di numerazione usuale e’detto POSIZIONALE o polimoniale in quanto il numero rappresentato e’ dato dal valore di un polinomio i cui coefficienti ( detti pesi ) sono le potenze intere e positive di 10 ( base del sistema di numerazione ) e percio’ogni cifra da’ al valore del polinomio un contributo dipendente dalla propria posizione e dal proprio valore:

•133 : 1x102 + 3x101 + 3x100

Ovvero 1x100 + 3x10 + 3x1

Il sistema romano, per esempio, e’invece “ additivo “ CXXXIII

Diapositiva 4

GC1 GREGORIO; 29/11/2007

Sistemi posizionali

Fondamenti di Informatica - Prof. Gregorio Cosentino12/02/2011 5

125.42

100 10-1 10-2101102

• Se la base è b occorrono b simboli:– b = 10 {0,9}– b = 2 {0,1}– b = 8 {0,1, ... 7}– b = 16 {0,1, ... 9,A,B,C,D,E,F}

N=Σ ai b ii=-k

m

am am-1 .... a0 . a-1 a-2 ... a-k

0 <= ai <= b-1b = base

• Ciascuna cifra rappresenta il coefficiente di una potenza della base

• L’esponente è dato dalla posizione della cifra

Sistema decimale-binario

Fondamenti di Informatica - Prof. Gregorio Cosentino12/02/2011 6

L’adozione, quasi universale, della base dieci è stata indubbiamente imposta dall’anatomia delle mani, perché sulle dieci dita l’uomo ha imparato a contare.

Quando si debba costruire un calcolatore in base dieci occorre naturalmente disporre dielementi fisici capaci di rappresentare le cifreda 0 a 9.Per esempio nei vecchi calcolatori da tavolo questo e’ realizzato con ruote che hanno dieciposizioni angolari stabili, ciascuna rappresentante una cifra.

Sistema decimale-binario

Nei calcolatori elettronici e’ invece necessario fare uso di elementi a due soli stati – dispositivi bistabili, componenti elettronici che funzionano in on/off, cioècon le condizioni di acceso/spento oppure di si/no - per questo motivo e’conveniente adottare un sistema con base due anzichè dieci. Un numerale sarà perciò una successione di zeri e di uni, ciascuno affetto da un peso che sarà una potenza intera di due.

La cifra binaria si chiama “ bit “ da “binary digit “ appunto cifra binaria.Nella memoria di un calcolatore si fa riferimento non ad un bit ma ad un ottetto di bit, chiamato byte.

Fondamenti di Informatica - Prof. Gregorio Cosentino12/02/2011 7

Conversione decimale-binario

Fondamenti di Informatica - Prof. Gregorio Cosentino12/02/2011 8

Conversione decimale-binario

• Si effettuano divisioni ripetute per 2• Il resto delle divisioni fornisce le cifre del numerale binario (a partire dalla meno significativa)

ES (26)10 =(11010)

26 136310

01011

cifra meno significativa

cifra più significativa

• Altrimenti si determina ad occhio quali potenze di 2 sono contenute nel numero

ES (26)10 =1·16+1·8+0·4+1·2+0·1Fondamenti di Informatica - Prof. Gregorio Cosentino12/02/2011 9

Ordini di grandezza• Il meccanismo è facilissimo, purchè si

Fondamenti di Informatica - Prof. Gregorio Cosentino12/02/2011 10

conoscano le potenze di due !!!!!

• Le potenze di 2 potenze di 1020 ... 29 = 1, 2, 4, 8, 16, 32, 64, 128, 256, 512

210 = 1.024 ~ 103 1K

220 = 210 210 =1.048.576 ~ 106 1M

230 = 210 210 210 =1.073.741.824 ~ 109 1G

240 = ... =1.099.511.627.770 ~ 1012 1T

I prefissi Kilo,Mega, Giga, Tera, etc sono per convenzione associati a potenze di 10

ES 226 = 2 6 220 = 64 M

Il numero di bit di un indirizzo binario determina le dimensioni della memoria

Intervalli rappresentati

• Rappresentando gli interi positivi e lo zero in

Fondamenti di Informatica - Prof. Gregorio Cosentino12/02/2011 11

notazione binaria con n cifre (bit) si copre l’intervallo [0 , 2n-1]

• Si sfruttano tutte le 2n disposizioni

ES n=3 [0,7]0 0001 0012 0103 0114 1005 1016 1107 111

Usando solo tre digit posso rappresentare 23

interi decimali, da zero incluso a sette incluso

NB Anche gli 0 non significativi devono essere rappresentati

Fondamenti di Informatica - Prof. Gregorio Cosentino12/02/2011 12

Rappresentazione valori interi negativi

Esistono diversi metodi di codifica

• Modulo e segno

• Complemento a uno (obsoleto)

• Complemento a due

• Eccesso 2m-1

Interi positivi e negativi

•1) Modulo e segno (il piu’ vecchio, semplice e intuitivo)

– un bit per il segno 0= + 1= -– i rimanenti n-1 bit valore assoluto del numero

- intervallo [-2n-1+1, +2n-1-1]

•Esempio per n=5-15 |15| = (1111)2 -15 = (11111)2

+15 |15| = (1111)2 +15 = (01111)2NB

– intervallo simmetrico– doppia rappresentazione dello zero (00000,10000)

– necessario trattare in maniera esplicita il segno, per esempio nel caso di somma algebrica di due operandi, quindi dispositivi di calcolo più complessi

– quindi poco usata a vantaggio del complemento a due

Fondamenti di Informatica - Prof. Gregorio Cosentino12/02/2011 13

2) Complemento a 1(Obsoleto)

Per cambiare di segno si complementa il numerale bit a bit (realizzato con la funzione NOT)

• I numerali positivi iniziano per 0, i negativi per 1

ES n=4 bit (3+1 segno)intervallo [-7, +7]5 = 0101

-5 = 1010

Complementare = cambiare segnoDoppia rappresentazione dello 0( +0 = 0000, -0 = 1111)

Fondamenti di Informatica - Prof. Gregorio Cosentino12/02/2011 14

3) Complemento a 2

• I positivi hanno la stessa rappresentazione che in complemento a 1

• I negativi si ottengono sommando 1 alla loro rappresentazione in complemento a 1

•Regola pratica per complementare:

Partendo da destra nella rappresentazione binaria si lasciano invariati tutti i bit fino al primo 1 compreso, e poi si complementa bit a bit

ESn=4 bit (3 + 1 segno)+5 = 0101 coincide con binaria-5 = 1011

Fondamenti di Informatica - Prof. Gregorio Cosentino12/02/2011 15

Fondamenti di Informatica - Prof. Gregorio Cosentino12/02/2011 16

Numeri negativi di otto bit nei quattro diversi sistemi

Esercizio

Fondamenti di Informatica - Prof. Gregorio Cosentino12/02/2011 17

• La conversione del numero decimale –712 con 16 bit in complemento a due è:

a) 1111 1101 0011 1000b) 1111 1101 0011 0111c) 1111 1101 0011 0110

• Motivare brevemente la risposta (massimo tre righe)

Soluzione Esercizio

• La conversione del numero

Fondamenti di Informatica - Prof. Gregorio Cosentino12/02/2011 18

decimale –712 con 16 bit in complemento a due è:

a) 1111 1101 0011 1000b) 1111 1101 0011 0111c) 1111 1101 0011 0110

Motivare brevemente la risposta (massimo tre righe)

• Da decimale a binario:• 10.1100.1000• Complemento a due e estendo

il segno negativo:• 1111 11-01 0011 1000

Esercizio

• Si determinino le rappresentazioni in modulo e segno e in complemento a 2 su 6 bit dei seguenti numeri decimali interi:

• +27• -10• +34• -3• -32• -17

Fondamenti di Informatica - Prof. Gregorio Cosentino12/02/2011 19

Numerali e numeri

Fondamenti di Informatica - Prof. Gregorio Cosentino12/02/2011 20

• Un numerale è solo una stringa di cifre• Un numerale rappresenta un numero solo se si specifica un sistema di numerazione

• Lo stesso numerale rappresenta diversi numeri in diverse notazioni

ESil numerale 110100 rappresenta:– Centodiecimilacento in base 10– (+52)10 in binario naturale– (-11)10 in complemento a 1– (-12)10 in complemento a 2

Aritmetica Binaria

Le regole che caratterizzano l’aritmetica binaria sono analoghe alle regole ben conosciute che valgono nel sistema decimale, con il necessario adattamento derivante dall’uso limitato ai due simboli 0 e 1.

Fondamenti di Informatica - Prof. Gregorio Cosentino12/02/2011 21

Addizioni binarie

0 + 0 = 00 + 1 = 11 + 0 = 11 + 1 = 0 con il riporto di 1

• Le addizioni fra numerali si effettuano cifra a cifra (come in decimale) portando il riporto alla cifra successiva; sono realizzate con la funzione XOR

ES3 + 2 = 5 0011 +

0010 = 0101

Se il numero di cifre non permette di rappresentare il risultato si ha un

trabocco nella propagazione del riporto

Fondamenti di Informatica - Prof. Gregorio Cosentino12/02/2011 22

Addizioni binarie

Fondamenti di Informatica - Prof. Gregorio Cosentino12/02/2011 23

Addizioni binarie

0 + 0 = 00 + 1 = 11 + 0 = 11 + 1 = 0 con il riporto di 1

Fondamenti di Informatica - Prof. Gregorio Cosentino12/02/2011 24

Se il numero di cifre non permette di rappresentare il risultato si ha un

trabocco nella propagazione del riporto

Per la somma di due numeri positivi di lunghezza K possono essere necessari K+1 bit. Se sono disponibili solo K cifre si genera un errore di overflow (o trabocco). Esempio con K=5:A =110112=2710 B = 001102=610 110112+001102 = 10000122710 + 610 = 3310

Esercizio Addizioni binarie

0 + 0 = 00 + 1 = 11 + 0 = 11 + 1 = 0 con il riporto di 1

Fondamenti di Informatica - Prof. Gregorio Cosentino12/02/2011 25

Effettuare la seguente operazione tra numeri binari, ipotizzando di lavorare con un elaboratore con lunghezza di parola (word) pari a un byte (8 bit):

42 + 31

Soluzione Esercizio

0 + 0 = 00 + 1 = 11 + 0 = 11 + 1 = 0 con il riporto di 1

Fondamenti di Informatica - Prof. Gregorio Cosentino12/02/2011 26

Effettuare le seguenti operazioni tra numeri binari, ipotizzando di lavorare con un elaboratore con lunghezza di parola (word) pari a un byte (8 bit):

42 + 31

Soluzione 42 + 31 = 0010 1010 + 0001 1111 Svolgendo i calcoli, si trova: 0010 1010 + 0001 1111 = -------------0100 10012 =7310

Esercizi Addizioni binarie

0 + 0 = 00 + 1 = 11 + 0 = 1

Fondamenti di Informatica - Prof. Gregorio Cosentino12/02/2011 27

1 + 1 = 0 con il riporto di 1

Eseguire le seguenti somme nel sistema binario:

101011 + 10111 =

11111 + 101111 =

1100111 + 10111 =

10101111 + 1111111 =

Rappresentazione valori interi

positivi e negativi

•Perché usare la rappresentazione in complemento?

•Semplifica le operazioni aritmetiche

•La differenza X – Y può essere calcolata mediante la somma dei complementi: C(x-y)=C(x)+C(-y)

•Semplificazione dei circuiti elettronici che eseguono le operazioni

Fondamenti di Informatica - Prof. Gregorio Cosentino12/02/2011 28

La differenza X – Y può essere calcolata

mediante la somma dei complementi:

C(x-y)=C(x)+C(-y)

Fondamenti di Informatica - Prof. Gregorio Cosentino12/02/2011 29

Fermiamoci per semplicitàa quattro digit

X – Y = C(X) + C(-Y);X=5 Y=3 >>>>>X-Y = 2C(5) = 0101C(-3)= 1101Sum = 0010 >>>>>>>>> 2

Rapresentazione di numeri reali

•Rappresentazione della retta reale•I numeri reali possono essere messi in corrispondenza biunivoca con i punti di una retta, detta retta numerica o

Fondamenti di Informatica - Prof. Gregorio Cosentino12/02/2011 30

retta reale.

Fondamenti di Informatica - Prof. Gregorio Cosentino12/02/2011 31

Rapresentazione di numeri reali

• Con un numero finito di cifre è solo possibile rappresentare un numero razionale che approssima con un certo errore il numero reale dato

• Vengono usate due notazioni:

A) Notazione in virgola fissaDedica parte delle cifre alla parte intera e le altre alla parte frazionaria

+ XXX .YY -> +25,33

B) Notazione in virgola mobileDedica alcune cifre a rappresentare un esponente della base che indica l’ordine di grandezza del numero rappresentato

Codice

Fondamenti di Informatica - Prof. Gregorio Cosentino12/02/2011 32

Regola che associa ai simboli o sequenze di simboli di un insieme A, simboli o sequenze

di simboli di un nuovo insieme B.

Un codice può essere rappresentato da una tabella, in cui ai caratteri di A (es. numeri,

lettere e altri simboli) corrispondono sequenze di simboli in B (es. 0 e 1)( come nel

codice ASCII ).

Esistono dei codici in cui alcune corrispondenze non sono univoche tra i

simboli dei due insiemi (rappresentazioni). Ad esempio nel codice con complemento a 1,

ci sono due codifiche per lo zero.

Codice ASCII

Fondamenti di Informatica - Prof. Gregorio Cosentino12/02/2011 33

•La sigla "ASCII" sta per: "American Standard Code for Information Interchange", cioe' "Standard americano per lo scambio di informazioni". È un codice che sfrutta 7 bit quindi vengono codificati 27 caratteri cioè128 caratteri (la numerazione va quindi da 0 a 127).

•il codice ASCII e' la rappresentazione numerica di un carattere in quanto il computer puo' solo capire numeri e codici. Per esempio il carattere "@" e' rappresentato dal codice ASCII "64", "Y" dall'"89", "+" dal "43", ecc.Pero' un codice ASCII puo' anche rappresentare una specifica azione, come "vai a capo", codice ASCII "10", oppure "cancella", codice "127", ecc.

Codice ASCII

Fondamenti di Informatica - Prof. Gregorio Cosentino12/02/2011 34

•Il codice ASCII fu inventato molti anni fa per le comunicazioni fra telescriventi (infatti ci sono dei codici di comandi specifici che sono quasi incomprensibili, ma al tempo avevano la loro funzione), poi man mano e' diventato uno standard mondiale.Parlando di un caso piu' pratico, quando qualcuno richiede un testo in formato ASCII, per esempio il vostro curriculum, oppure un articolo, ecc, significa che richiede un testo nel formato standard in modo che possa facilmente riutilizzarlo nei propri programmi.

•Infatti il formato ASCII e' universalmente riconosciuto da tutti i computer, cosa che non e' vera nel caso di testi "formattati", cioe' con sottolineature, stili, grassetti, ecc.Un file in formato ASCII puo' essere creato utilizzando il Blocco Note di Windows, oppure salvando in formato "solo testo" da un qualsiasi programma di videoscrittura, come Word o simili.

Codice ASCII

Fondamenti di Informatica - Prof. Gregorio Cosentino12/02/2011 35

Codice ASCII

I primi 32 caratteri non sono stampabili o visualizzabili e servono per il controllo della visualizzazione a video, della stampa, ecc.;

Fondamenti di Informatica - Prof. Gregorio Cosentino12/02/2011 36

Codice ASCII

Fondamenti di Informatica - Prof. Gregorio Cosentino12/02/2011 37

I rimanenti caratteri sono visualizzabili e comprendono le cifre, i caratteri , la punteggiatura e i simboli particolari.

Fondamenti di Informatica - Prof. Gregorio Cosentino12/02/2011 38

Codice UNICODE

•Il Codice ASCII è a 7 bit, poi esteso a 8•Codice UNICODE a 16 bit, nuova proposta di standard:

– 65.536 code points– Semplifica la scrittura del software– 336 code points: alfabeti latini– 112 accenti e simboli diacritici– Greco, cirillico, ebraico, ecc.– 21.000 ideogrammi cinesi– 11.000 sillabe coreane ……

•La versione 3.0 di UNICODE (Febbraio 2000) definisce 49194 caratteri. Un consorzio assegna quello che resta, ma durerà poco.