Aritmética - UFPR

Cap?tulo 6

Aritm?tica

You cannot ask us to take sides against arithmetic. Winston Churchill

Computadores foram inventados, e s?o usados, para efetuar opera??es aritm?ticas sobre n?meros em aplica??es t?o diversas como o processamento da folha de pagamentos de uma empresa, na simula??o de trajet?rias de planetas e de part?culas subat?micas, na simula??o de paisagens em jogos, no c?lculo do pre?o a pagar pelo etanol num posto de combust?veis. Neste cap?tulo1 estendemos nossa abstra??o para bits, permitindo agora que tuplas de bits representem n?meros naturais e n?meros inteiros. Circuitos de aritm?tica normalmente empregam a representa??o para inteiros chamada de complemento de dois porque esta ? simples e eficaz, e resulta em circuitos tamb?m simples, portanto eficazes. Esta representa??o ? definida na Se??o 6.1. Neste cap?tulo estudamos os circuitos usados para computar a soma, a diferen?a e o produto de dois n?meros representados por sequ?ncias de bits. Os circuitos que efetuam estas opera??es s?o descritos nas Se??es 6.2 e 6.3. Deslocamentos s?o opera??es interessantes: um deslocamento para a esquerda equivale a uma multiplica??o por uma pot?ncia de dois, enquanto um deslocamento para a direita, tomados os cuidados necess?rios, equivale a uma divis?o por uma pot?ncia de dois. Estes circuitos s?o apresentados na Se??o 6.4. O componente de um processador em que s?o efetuadas somas e subtra??es, mais as opera??es l?gicas sobre vetores de bits, ? chamado de Unidade de L?gica e Aritm?tica, e sua implementa??o ? descrita na Se??o 6.5. O algoritmo que usamos para somar dois n?meros implica na propaga??o do vai-um, potencialmente atrav?s de todos os d?gitos dos operandos. Num somador com operandos de 32 ou 64 bits, o tempo necess?rio para computar o resultado pode ser excessivo. Nas Se??es 6.6 e 6.7 veremos dois somadores que minimizam o tempo de propaga??o do vai-um. Na Se??o 6.8 s?o apresentados tr?s circuitos combinacionais que efetuam a multiplica??o. Na multiplica??o, como na soma, a cadeia de propaga??o do vai-um ? problem?tica e seus efeitos no tempo de propaga??o devem ser minimizados.

1? Roberto Andr? Hexsel, 2012-2021. Vers?o de 25 de fevereiro de 2021.

144

Cap?tulo 6. Aritm?tica

145

6.1 Sequ?ncias de Bits Que Representam N?meros

N?meros devem ser representados internamente ao computador por sequ?ncias de bits, uma vez que os bits s?o as menores unidades de informa??o que podem ser usadas num computador digital. Vejamos ent?o como n?meros naturais e n?meros inteiros podem ser representados como sequ?ncias de bits. Iniciamos a explora??o pela adi??o, que ? opera??o aritm?tica mais simples, e a mais popular nos programas que escrevemos.

6.1.1 Adi??o na base 2

A soma s de dois n?meros a e b, representados em um ?nico d?gito bin?rio ?:

a+b=s

N

0+0=0

0

0+1=1

1

1+0=1

1

1+1=?

2

A coluna da direita mostra o n?mero natural que representa o resultado. Na quarta linha, a soma 1 + 1 = 2 n?o ? represent?vel por um ?nico d?gito, e portanto a tabela verdade da soma deve ser aumentada com uma coluna para o vai-um.

Se inclu?mos o vai-um no resultado, que incluamos tamb?m o vem-um nas parcelas. O resultado da soma ? representado pelo n?mero de dois bits vai, s :

vem + a + b = vai s

N

0 +0+0= 0 0

0

0 +0+1= 0 1

1

0 +1+0= 0 1

1

0 +1+1= 1 0

2

1 +0+0= 0 1

1

1 +0+1= 1 0

2

1 +1+0= 1 0

2

1 +1+1= 1 1

3

(6.1)

Como o resultado da adi??o de tr?s bits (1+1+1 = 3) ? represent?vel em dois d?gitos (3 = 112), todas as oito combina??es das entradas produzem os resultados esperados.

6.1.2 Sequ?ncias de Bits Que Representam Inteiros

Qual seria ent?o uma representa??o para n?meros, usando bits? Uma primeira restri??o, que deriva de custo e da tecnologia dispon?vel, ? que os n?meros sejam representados por sequ?ncias de bits com tamanho fixo, cujas larguras t?picas s?o de 8, 16, 32 ou 64 bits. Isso ? necess?rio porque os circuitos que efetuam opera??es aritm?ticas devem ter tamanho finito, assim como deve ser finita a mem?ria que armazena os n?meros.

Felizmente, a forma mais ?bvia ? tamb?m a mais simples e eficaz: emprega-se a mesma nota??o posicional que usamos com n?meros na base 10, na qual cada d?gito, ou posi??o, ? multiplicada por uma pot?ncia de 10. Como a representa??o ? com bits, a base da representa??o ? 2.

Cap?tulo 6. Aritm?tica

146

Considere uma representa??o para n?meros naturais (N) com um campo fixo com 8 bits de largura, como a mostrada abaixo. A posi??o de cada d?gito bin?rio corresponde a uma pot?ncia de dois; o d?gito ? direita tem peso 20 = 1 enquanto o d?gito mais significativo tem peso 27 = 128. A faixa de valores represent?veis ? de 0 a 255. O n?mero 99 ? representado em bin?rio, num campo de 8 bits, por 0110.00112 = 26 + 25 + 21 + 20 = 64 + 32 + 2 + 1.

peso 27 26 25 24 23 22 21 20 99 0 1 1 0 0 0 1 1

Para uma representa??o com k bits de largura, o valor do n?mero natural N representado por uma sequ?ncia de k bits ? obtido com a Equa??o 6.2, e ? a soma ponderada dos bits bi, i [0, k).

k-1

N = 2i ? bi

i=0

(6.2)

Qual seria uma representa??o igualmente eficiente para n?meros inteiros (Z)? Dada a conveni?ncia da representa??o para os naturais, expressa na Equa??o 6.2, a representa??o para zero, em 8 bits, deve ser

0000.0000 .

Assim como para zero, a representa??o ?bvia para o n?mero +1 ?

0000.0001 .

Qual seria ent?o a representa??o para -1? Esta representa??o deve ser tal que -1 + 1 = 0 . Se somarmos +1 ao n?mero M que representa -1, obtemos:

00000001 + m7 m6 m5 m4 m3 m2 m1 m0

00000000

Da Equa??o 6.1 temos que 1 + 1 = 0 e vai um para a pr?xima posi??o. A soma 1 + m0 = 0 somente se m0 = 1. A soma de m0 = 1 com 1 ? zero e vai-um. Para o segundo d?gito, a soma vem-um + 0 + m1 = 0 somente se m1 = 1. Da mesma forma para o terceiro d?gito, com m1 = 1, obtemos m2 = 1. Continuando at? m7, descobrimos que a representa??o em 8 bits para -1 ? 1111.1111 .

Qual seria a representa??o para os demais n?meros negativos, de tal forma que A + (-A) = 0?

(+A) + (-A) = 0 -A = 0 - A = (1 - 1) - A = 1 + (-1 - A)

Espa?o em branco proposital.

Cap?tulo 6. Aritm?tica

147

Considerando somente o termo (-1 - A), qual o valor de R = (-1 - A)?

11111111

-1

- a7 a6 a5 a4 a3 a2 a1 a0

-A

r7 r6 r5 r4 r3 r2 r1 r0

R

Computando a subtra??o bit a bit, iniciando por a0, temos dois casos:

(i) se a0 = 0, ent?o r0 = 1 - 0 = 1 = a0 ;

e (ii) se a0 = 1, ent?o r0 = 1 - 1 = 0 = a0 .

Se aplicarmos o mesmo racioc?nio aos demais bits, descobre-se que R = (-1 - A) ? o complemento bit a bit de A, e ? representado por R = A. Assim,

-A = 1 + A

(6.3)

que ? a maneira simples, embora tediosa, de obter a representa??o de n?meros negativos: basta complementar bit a bit o n?mero positivo e somar 1 ao valor complementado. Esta representa??o ? chamada de complemento de dois, e nela o d?gito mais significativo ? sempre multiplicado por -2m para um m apropriado. Em n?meros representados em k bits, o bit bk-1 ? multiplicado por -2k-1. Se k = 4, ent?o o n?mero +3 ? representado por

+3 = 00112 = (0 ? -23) + 0 ? 22 + 1 ? 21 + 1 ? 20,

sendo -3 representado por

-3 = 11012 = (1 ? -23) + 1 ? 22 + 0 ? 21 + 1 ? 20.

O conjunto de n?meros inteiros representados em k bits ? [-2k-1, 2k-1 - 1]. Por causa da representa??o para zero, as 2k representa??es distintas s?o divididos em 2k-1 n?meros negativos e 2k-1 - 1 n?meros positivos.

A Equa??o 6.4 mostra os pesos dos d?gitos de um n?mero representado em 8 bits. O d?gito mais significativo ? multiplicado por -27, e os demais d?gitos s?o multiplicados por pot?ncias decrescentes positivas de 2.

X = (x7 ? -27) + x6 ? 26 + x5 ? 25 + ? ? ? + x2 ? 22 + x1 ? 21 + x0 ? 20

(6.4)

Se o d?gito mais significativo ? zero, ent?o o n?mero representado ? positivo, do contr?rio ? negativo. Logo, esse d?gito ? chamado de bit de sinal.

Espa?o em branco proposital.

Cap?tulo 6. Aritm?tica

148

Exemplo 6.1 Alguns exemplos de n?meros representados em complemento de dois, em 8 bits s?o mostrados na Tabela 6.1. A posi??o mais significativa ? multiplicada por 1 nos n?meros negativos e portanto esta parcela vale -128 do valor representado. Para representar um n?mero maior do que -128, outras parcelas positivas devem ser adicionadas para descontar a diferen?a do valor desejado para -128. Como mostra a segunda linha da tabela, -1 = -128 + 127.

Tabela 6.1: Exemplos de representa??o em complemento de dois.

posi??o b7 b6 b5 b4 b3 b2 b1 b0

valor

peso -128 64 32 16 8 4 2 1

+1 = +0 + 1

0 0 0 00001

-1 = -128 + 127 1 1 1 1 1 1 1 1

-125 = -128 + 3

1 0 0 00011

-4 = -128 + 124 1 1 1 1 1 1 0 0

Considerando que num circuito digital as opera??es s?o efetuadas em circuitos com largura fixa e finita, o que ocorre quando somamos dois n?meros grandes? Se somarmos o maior n?mero represent?vel a si pr?prio, ele dobra de tamanho:

N + N = 2N, log2(N ) = k, log2(2N ) = k + 1.

A soma de dois n?meros de k bits tem k + 1 bits por causa da possibilidade de ocorrer vai-um no d?gito mais significativo. Isso significa que o resultado de uma soma pode ser maior do que o maior n?mero que pode ser representado em k bits. Esta situa??o indica a ocorr?ncia de overflow porque um bit do resultado `transborda' para al?m do limite m?ximo da representa??o.

Felizmente, o algoritmo para a detec??o de overflow ? simples. Para n?meros representados em k bits e opera??o A + B = R:

1. replique o d?gito mais significativo das duas parcelas, representando os operandos em k + 1 bits (ak = ak-1 e bk = bk-1);

2. adicione os dois operandos de k + 1 bits e ignore o vai-um para a posi??o rk+1;

3. ocorre overflow se, e somente se, os dois bits mais significativos do resultado diferem (rk-1 = rk); do contr?rio, a resposta ? o n?mero representado corretamente em k bits.

Exemplo 6.2 Pode o resultado de 7 + 6 ser representado corretamente em 4 bits?

Na opera??o abaixo, o d?gito replicado est? sublinhado, e o vai-um ? mostrado ? esquerda do d?gito

que o recebe.

0 1+0 1+1 1 1

7

+0 0 1 1 0

+6

0 1 1 01

+13

r4 r3 r2 r1 r0

Os bits r3 e r4 diferem e portanto 7 + 6 n?o pode ser representado em 4 bits porque o maior n?mero representado corretamente com k = 4 ? 24-1 - 1 = 7.

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download