Rappresentazione binaria
dei numeri interi senza segno
Conversione Decimale-Binario:
55 mod 2 =1 = a0
(55 div 2) mod 2 = 27 mod 2 = 1 = a1
((55 div 2) div 2) mod 2= (27 div 2) mod 2=13 mod 2=1=
a2
(13 div 2) mod 2= 6 mod 2 = 0 =a3 (6 div 2) mod 2 = 3 mod 2 = 1 =a4 (3 div 2) mod 2 = 1 mod 2 = 1 = a5 Dunque:
5510=1101112
Conversione Binario-Esadecimale:
1) Raggruppo i bit a blocchi di 4:
11 0111
2) Converto ciascun blocco in base 16 112=316 01112=716
Dunque: 1101112 = 3716
00110111 37
Conversione Binario-Decimale:
01010010 =0*20+1*21+0*22+0*23+1*24+0*25+1*26+0*27=
=2+16+64=8210
Conversione Binario-Esadecimale:
1) Raggruppo i bit a blocchi di 4:
0101 0010
2) Converto ciascun blocco in base 16 01012=516 00102=216
=>5216
82 52
00110111 37
Conversione Esadecimale-Decimale:
A7 =10*161+7*160=10*16+7=167 3E = 3*161+E*161=48+14=62
Conversione Esadecimale-Binario:
1) Traduco ciascuna cifra esadecimale in un blocco di 4 bits :
A16 = 1010= 23+21=10102 716 = 710= 22+21+20=01112 2) Il binario corrispondente si ottiene
sostituendo ciascuna cifra esadecimale con il relativo blocco di 4 bit:
A716=101001112
167
52
00110111 37
82
62
10100111
Somma tra Numeri Binari Interi Positivi
Regole base:
• 0+0=0
• 0+1=1+0=1
• 1+1=0 con riporto di 1
• 1+1+(1)=1 con rip.1, dove (1) e’ il riporto proveniente dallo step precedente
Esempio:
0 0 0 0 1 1 1 0 riporti 0 0 1 0 1 1 1 0 +
0 1 0 0 0 1 1 1 = --- 0 1 1 1 0 1 0 1
1 0 0 0 1 1 1 0 riporti 1 0 1 0 1 1 1 0 +
1 1 0 0 0 1 1 1 = --- 1 1 1 1 0 1 0 1 Un trabocco indica
un overflow
Sottrazione tra Numeri Binari Interi Positivi
Regole base:
• 0-0=0
• 0-1=1 con prestito di 1
• 1-0=1
• 1-1=0
Esempio:
0 1 0 0 0 1 1 1 prestiti 1 0 1 0 1 1 1 0 -
0 1 0 0 0 1 1 1 = --- 0 1 1 0 0 1 1 1
1 1 0 1 1 1 1 1 prestiti 1 0 1 0 0 1 1 0 -
1 1 0 0 0 1 1 1 = --- 1 1 0 1 1 1 1 1 Un trabocco indica
un underflow.
Moltiplicazione tra Numeri Binari Interi Positivi
• La moltiplicazione puo’ essere realizzata banalmente sommando al moltiplicando se stesso, un numero di volte pari al valore del moltiplicatore. 5*3=5+5+5=15.
• Assumendo che la somma abbia costo costante operando su addendi
rappresentabili con un numero di bits noto a priori, tale algoritmo ha complessità
computazionale pari a O(N), dove N è il valore del moltiplicatore.
• Se moltiplicando e moltiplicatore sono rappresentati con k bits, il prodotto può richiedere fino a un max di 2k bits per la sua rappresentazione.
00110 x 00101 = 00110
00000 00110 00000 00000
000011110
somme
parziali
Moltiplicazione tra Numeri Binari Interi Positivi: Potenze di 2
• Nel caso di moltiplicazione per potenza k-esima di 2 il risultato è uno shift a
sinistra di k posizioni:
00110 x 10 = 00000
00110 001100
00110 x 100 = 00000
00000 00110
0011000
Divisione tra Numeri Binari Interi Positivi
10011011 1001 1001 10001
00001011 1001 0010
Verifichiamo la correttezza del calcolo:
1001*
10001=
1001 0000 0000 0000 1001
10011001+
0010=
(resto)10011011
resto
quoziente
Divisione tra Numeri Binari Interi Positivi: Potenze di 2
• Nel caso di divisione per potenza k-esima di 2 il risultato è uno shift a destra di k posizioni:
10011011 1000 1000 10011
0001101
1000
1011
1000
11
Rappresentazione binaria
dei numeri interi con segno
101011012 = 1+4+32+128 =16510 (senza segno) 101011012=-1*(1+4+8+32)=-4510 (segno e modulo) 101011012=-1*27+1+4+32=-9110 (complemento a 2)
per verificare: a) invertiamo 1 con 0 e viceversa: 0101000102, b) sommiamo 1: 0101000112=91
Proprietà della rappresentazione in complemento a 2:
1) L’operazione di cambiamento di segno è eseguibile complementando alla base 2) La sottrazione si può ricondurre ad una somma (vedi prox slide)
3) E’ possibile rappresentare lo stesso numero con un numero maggiore di bit semplicemente copiando il bit + significativo:
es: -710=10012 (con 4 bit)=111110012 (con 8 bit)= 11111111111110012
Somma tra Numeri Binari in Complemento a 2
• Siano a e b due numeri e sia R(a) e R(b) la rappresentazione di a e b in complemento alla base (ad es. base 2)
• Sommando R(a) ed R(b), e ignorando l’eventuale riporto dalla posizione più significativa, otteniamo R(a+b).
• A meno che non vi sia discordanza tra il segno del risultato e quello comune dei due addendi (ovvero a>0,b>0,a+b<0 oppure
a<0,b<0,a+b>0): in tal caso si ha un supero di capacità.
00102+11012=11112 [2 + (-3) = -1] riporto 0000 0010+
1101=
1111 01102+01112=OVERFLOW[6 + 7 = 13>7!] riporto 0110
0110 0111
In generale per calcolare a – b basta:
1) Trovare il complemento a 2 di b, cioè -b 2) Sommare a+(-b)
Somma tra Numeri Binari in Complemento a 2
• Siano a e b due numeri e sia R(a) e R(b) la rappresentazione di a e b in complemento alla base (ad es. base 2)
• Sommando R(a) ed R(b), e ignorando l’eventuale riporto dalla posizione più significativa, otteniamo R(a+b).
• A meno che non vi sia discordanza tra il segno del risultato e quello comune dei due addendi (ovvero a>0,b>0,a+b<0 oppure
a<0,b<0,a+b>0): in tal caso si ha un supero di capacità.
11112+10002=OVERFLOW [-1 + (-8) = -9<-8] riporto 1000 1111+
1000=
0111 01102+11112=0111 [6 + (-1) = 5] riporto 1110
0110 1111 0101 L’overflow è possibile solo se gli
addendi hanno segno comune!