5-OPINT

Prévia do material em texto

Sistemas de Computação
Operações Aritméticas com InteirosOperações Aritméticas com Inteiros
Sistemas de Computação
Soma de números sem sinal
• Soma padrão
– Ignora o “vai um” (carry)
• Implementa aritmética modular
s = UAddw(u , v) = u + v mod 2w
UAddw(u,v) 
u v u v  2w
u v  2w u v  2w



• • •
• • •v+
• • •u + v
• • •
Soma verdadeira: w+1 bits
Operandos: w bits
Descarta o “vai um”
(carry): w bits
UAddw(u , v)
u
Sistemas de Computação
Visualizando a soma de inteiros sem 
sinal
0 2 4 6 8 10 12 14
0
2
4
6
8
10
12
14
0
4
8
12
16
20
24
28
32
Integer Addition
• Soma de inteiros
– inteiros de 4-bit u, v
– Calcula soma verdadeira 
Add4(u , v)
– Valores aumentam 
linearmente com u e v
– Forma uma superfície 
plana
Add4(u , v)
u
v
Sistemas de Computação
Visualizando a soma de inteiros sem 
sinal em C
0 2 4 6 8 10 12 14
0
2
4
6
8
10
12
14
0
2
4
6
8
10
12
14
16
• Descarta “vai um”, se 
soma real  2w
0
2w
2w+1
UAdd4(u , v)
u
v
Soma real
Soma modular
Overflow
Overflow
Sistemas de Computação
Soma de números em complemento a 2
• TAdd e UAdd possuem o mesmo comportamento no 
nível de bits
– Soma com sinal vs. sem sinal em C:
int s, t, u, v;
s = (int) ((unsigned) u + (unsigned) v);
t = u + v
– Terá como resultado s == t
• • •
• • •
u
v+
• • •u + v
• • •
Soma real: w+1 bits
Operandos: w bits
Descarta o “vai 
um”(carry): w bits
TAddw(u , v)
Sistemas de Computação
Caracterizando TAdd
• Funcionalidade
– Soma real requer w+1
bits
– Joga fora MSB
– Trata bits que 
permanecem como 
inteiro compl. a 2
–2w –1
–2w
0
2w –1
2w–1
Soma verdadeira
Resultado TAdd
1 000…0
1 100…0
0 000…0
0 100…0
0 111…1
100…0
000…0
011…1
PosOver
NegOver
TAdd w (u,v ) 
u  v  2 w u  v  TMin w
u  v TMin w  u  v  TMax w
u  v  2 w TMax w  u  v
(NegOver)
(PosOver)u
v
< 0 > 0
< 0
> 0
NegOver
PosOver
TAdd(u , v)
Sistemas de Computação
Visualizando soma em complemento a 2
-8 -6 -4 -2 0 2 4 6
-8
-6
-4
-2
0
2
4
6
-8
-6
-4
-2
0
2
4
6
8
• Valores
– comp. a 2 com 4 bits
– Valores entre -8 to +7
• Descarta “vai um”
– Se soma  2w–1
• Se torna negativa
– Se soma < –2w–1
• Se torna positiva
TAdd4(u , v)
u
v
PosOver
NegOver
Sistemas de Computação
Detectando overflow em complemento a 
2
• Tarefa
– Dada s = TAddw(u , v)
– Determine se s = Addw(u , v)
– Exemplo
int s, u, v;
s = u + v;
• Situações de overflow
– u, v < 0, s  0 (NegOver)
– u, v  0, s < 0 (PosOver)
ovf = (u<0 == v<0) && (u<0 != 
s<0);
0
2w –1
2w–1
PosOver
NegOver
-2w–1
-2w
Sistemas de Computação
Obtendo representação de números 
negativos em complemento a 2
• Para representação em complemento a 2
~x + 1 == -x
• Complemento
– Observação: ~x + x == 1111…112 == -1
• Incremento
– ~x + x + (-x + 1) == -1 + (-x + 1)
– ~x + 1 == -x
1 0 0 1 0 11 1x
0 1 1 0 1 00 0~x+
1 1 1 1 1 11 1-1
Sistemas de Computação
Exemplos de representação 
complemento a 2
Decimal Hexa Binário
x 15213 3B 6D 00111011 01101101
~x -15214 C4 92 11000100 10010010
~x+1 -15213 C4 93 11000100 10010011
y -15213 C4 93 11000100 10010011
x = 15213
Decimal Hexa Binário
0 0 00 00 00000000 00000000
~0 -1 FF FF 11111111 11111111
~0+1 0 00 00 00000000 00000000
0
Sistemas de Computação
Multiplicação
• Cálculo do produto exato dos números (com sinal ou sem 
sinal) x, y com w bits
• Faixas de valores
– Sem sinal: 0  x * y  (2w – 1) 2 = 22w – 2w+1 + 1
• Até 2w bits
– Valor min. compl. a 2: x * y  (–2w–1)*(2w–1–1) = –22w–2 + 2w–1
• Até 2w–1 bits
– Valor máximo compl. a 2: x * y  (–2w–1) 2 = 22w–2
• Até 2w bits, mas somente para (TMinw)2
• Mantendo resultados exatos
– Precisa manter a expansão do tamanho da palavra para cada produto calculado
– Realizado em software por pacotes aritméticos com precisão arbitrária
Sistemas de Computação
Multiplicação sem sinal em C
• Função de multiplicação padrão
– Ignora w bits de mais alta ordem
• Implementa aritmética modular
UMultw(u , v)= u · v mod 2w
• • •u
v*
u · vProduto verdadeiro: 2*w bits
Operandos: w bits
Descarta w bits: w bits UMultw(u , v)
• • •
• • •• • •
• • •
Sistemas de Computação
Multiplicação com sinal vs. Sem sinal
• Multiplicação sem sinal
unsigned ux = (unsigned) x;
unsigned uy = (unsigned) y;
unsigned up = ux * uy
– Trunca o produto para número com w bits up = UMultw(ux, uy)
– Aritmética modular: up = ux  uy mod 2w
• Multiplicação complemento a 2
int x, y;
int p = x * y;
– Calcula o produto exato de dois números x, y com w bits 
– Trunca resultado para número com w bits p = TMultw(x, y)
Sistemas de Computação
Multiplicação por potência de 2 através 
de deslocamento
• Operação
– u << k fornece u * 2k
– Para números com e sem sinal
• Exemplos
– u << 3 == u * 8
– u << 5 - u << 3 == u * 24
– Maioria das máquinas desloca e soma mais rápido que multiplica 
• Compilador gera o código automaticamente
• • •
0 0 1 0 0 0•••
u
2k*
u · 2kProduto verdadeiro: w+k bits
Operandos: w bits
Descarta k bits: w
bits
UMultw(u , 2k)
•••
k
• • • 0 0 0•••
TMultw(u , 2k)
0 0 0••••••
Sistemas de Computação
Divisão por potência de 2 para números 
sem sinal através de deslocamento
• Quociente da divisão de núm. sem sinal por potência de 2
– u >> k fornece  u / 2k 
– Utiliza deslocamento lógico
Divisão Calculada Hexa Binário
x 15213 15213 3B 6D 00111011 01101101
x >> 1 7606.5 7606 1D B6 00011101 10110110
x >> 4 950.8125 950 03 B6 00000011 10110110
x >> 8 59.4257813 59 00 3B 00000000 00111011
0 0 1 0 0 0•••
u
2k/
u / 2kDivisão: 
Operandos:
•••
k
••• •••
•••0 ••• •••
 u / 2k  •••Resultado:
,
Vírgula binária
0 •••
Sistemas de Computação
Divisão por potência 2 para números 
com sinal através de deslocamento
• Quociente da divisão de número com sinal por 
potência de 2
– x >> k fornece  x / 2k 
– Utiliza deslocamento aritmético 
– Arredonda para direção errada quando u < 0
0 0 1 0 0 0•••
x
2k/
x / 2kDivisão:
Operandos:
•••
k
••• •••
•••0 ••• •••
Arr. p. baixo(x / 2k) •••Resultado:
,
Vírgula binária
0 •••
Sistemas de Computação
Divisão por potência de 2 para números 
com sinal através de deslocamento
Divisão Calculado Hexa Binário
y -15213 -15213 C4 93 11000100 10010011
y >> 1 -7606.5 -7607 E2 49 11100010 01001001
y >> 4 -950.8125 -951 FC 49 11111100 01001001
y >> 8 -59.4257813 -60 FF C4 11111111 11000100