Multiplicação Binária de Números Inteiros

Prévia do material em texto

6-1
Capítulo
SEIS
Multiplicação e Divisão
6.1 Multiplicação binária (números inteiros positivos)
Em qualquer sistema de numeração, a multiplicação é uma forma resumida da soma repetitiva
de uma parcela consigo mesma (o multiplicando) um determinado número de vezes (dado
pelo multiplicador). Assim, a multiplicação ‘a x b’ significa ‘a + a + a + ... + a’, onde a
parcela ‘a’ se repete ‘b’ vezes. A soma repetitiva levaria entretanto muito tempo para ser
realizada, especialmente para números grandes. Assim, desenvolveu-se (para o sistema
decimal) um método que permitisse realizar a multiplicação de forma mais rápida. Cada
dígito do multiplicador multiplica individualmente o multiplicando e depois as parcelas
intermediárias são somadas. Deve-se notar que cada parcela, além de ser multiplicada pelo
dígito do multiplicador, também é multiplicada pelo peso deste dígito:
63
 123 
189 (63 x 3 x 1)
1260 (63 x 2 x 10)
 + 6300 (63 x 1 x 100)
7749
Para simplificar a notação, assume-se o peso do dígito implicitamente, deixando-se de
escrever os respectivos zeros. No lugar disto, simplesmente desloca-se cada parcela uma
casa decimal para esquerda:
63
 123 
189 (sem deslocamento: x 1)
126 (um deslocamento: x 10)
 + 63 (dois deslocamentos: x 100)
7749
Esta é a forma normal de realização da multiplicação decimal. A multiplicação binária é
realizada exatamente da mesma forma. Observe-se que um deslocamento para a esquerda, em
qualquer sistema de numeração, equivale a multiplicar pela base deste sistema. Assim, em
decimal, para multiplicar por dez simplesmente desloca-se todo o número uma casa para a
esquerda e acrescenta-se um ‘zero’ na posição menos significativa. O mesmo vale para o
sistema binário quando se quiser multiplicar por dois.
Em binário a tabela de multiplicação é extremamente simples. Note-se que, ao multiplicar-se
por zero, o resultado é zero, e ao multiplicar-se um número qualquer por um, o resultado é
este próprio número.
Multiplicando Multiplicador Resultado
0 0 0
0 1 0
1 0 0
1 1 1
6-2
A multiplicação segue o método da multiplicação decimal: analisa-se cada dígito do
multiplicador, da esquerda para direita; multiplica-se o multiplicando por cada um destes
dígitos; desloca-se o resultado intermediário de cada multiplicação cada vez uma casa a mais
para a esquerda; e finalmente soma-se todas as parcelas, formando o resultado final. Por
exemplo, sejam dois números de seis bits, em representação inteira positiva:
1 1 0 1 1 0
 x 1 1 0 0 1 1 
1 1 0 1 1 0
1 1 0 1 1 0
0 0 0 0 0 0
0 0 0 0 0 0
1 1 0 1 1 0
 + 1 1 0 1 1 0 
1 0 1 0 1 1 0 0 0 0 1 0
Quando um dígito do multiplicador for zero, o resultado da multiplicação intermediária
também será zero. Esta parcela pode então ser eliminada da soma final, pois não contribui
para o resultado:
1 1 0 1 1 0
 x 1 1 0 0 1 1 
1 1 0 1 1 0
1 1 0 1 1 0
1 1 0 1 1 0
 + 1 1 0 1 1 0 
1 0 1 0 1 1 0 0 0 0 1 0
Para um computador, somar diversas parcelas é bem mais complexo do que somar duas
parcelas. Assim, as parcelas intermediárias são somadas a medida em que são formadas:
1 1 0 1 1 0
 x 1 1 0 0 1 1 
1 1 0 1 1 0
 + 1 1 0 1 1 0 
1 0 1 0 0 0 1 0
 + 1 1 0 1 1 0 
1 0 0 0 0 0 0 0 0 1 0
 + 1 1 0 1 1 0 
1 0 1 0 1 1 0 0 0 0 1 0
No exemplo acima, multiplicou-se dois números de seis bits e obteve-se um resultado em 12
bits. De um modo geral, multiplicando-se um número de ‘n’ bits por outro de ‘m’ bits
obtém-se um resultado de ‘n+m’ bits. No caso dos computadores, que trabalham com
números de ‘n’ bits, a multiplicação produz números de ‘2n’ bits. Devido a este fato, nunca
ocorre estouro de representação. Para a multiplicação binária tem-se, até agora, o seguinte
método:
1. Início: i ‹ 0, resultado ‹ 0
2. Se o bit de ordem ‘i’ do multiplicador for zero, ir para 4.
3. Somar o multiplicando ao resultado (resultado ‹ resultado + multiplicando)
4. Deslocar o multiplicando para a esquerda (multiplicando ‹ multiplicando x 2)
5. Incrementar ‘i’ de uma unidade (i ‹ i + 1)
Se ‘i’ for menor que o número de bits do multiplicador, ir para 2.
Senão, terminar.
6-3
Devido ao fato de trabalhar com um número fixo de bits, não é tão simples para um
computador somar números de comprimentos diferentes. Assim, o método de multiplicação
ainda precisa ser melhor adaptado. Para tanto, devemos observar que:
• o bit menos significativo do resultado só é afetado pela primeira parcela da soma;
nenhuma outra parcela pode alterar mais este bit.
• generalizando, o ‘i-ésimo’ bit menos significativo do resultado só é afetado pelas
primeiras ‘i’ parcelas intermediárias. Por exemplo, o segundo bit do resultado só é
afetado pelas duas primeiras parcelas; o terceiro bit só é afetado pelas três primeiras
parcelas, e assim por diante.
• se uma das parcelas de uma soma deve ser deslocada para a esquerda, o mesmo
resultado é obtido deslocando-se a outra parcela para a direita.
Assim, a cada passo da multiplicação, no lugar de deslocar-se o multiplicando para a
esquerda, desloca-se o resultado para a direita. E os bits menos significativos do resultado,
um de cada vez, são armazenados em um elemento especial, pois não serão mais
modificados. Sejam então ‘M’ o multiplicando, em ‘n’ bits; ‘m’ o multiplicador, também em
‘n’ bits; ‘R’ os ‘n’ bits mais significativos do resultado; ‘r’ os ‘n’ bits menos significativos
do resultado; e ‘c’ o vai-um da soma (carry). Tem-se então o seguinte método:
1. Início: i ‹ 0, R ‹ 0, r ‹ 0
2. Se o bit de ordem ‘i’ de m for zero (mi=0), fazer c ‹ 0 e ir para 4.
3. Somar M a R (R ‹ R + M), c ‹ vai-um
4. Deslocar os ‘2n’ bits do resultado para direita, usando o ‘vai-um’ da soma
anterior como novo bit mais significativo do resultado (se não houve soma, usa-
se ‘0’):
( R r ) ‹ desl.direita( c R r )
5. Incrementar ‘i’ de uma unidade (i ‹ i + 1)
Se ‘i’ for menor que ‘n’, ir para 2. Senão, terminar.
Sejam por exemplo n = 6, M = 110110, m = 110011. Então tem-se:
1. i ‹ 0, R ‹ 000000, r ‹ 000000
2. m(0) = 1, continuar em 3
3. R ‹ 000000 + 110110 = 110110, c = 0
4. (R r) ‹ desl.direita(0 110110 000000) = (011011 000000)
5. i ‹ 1; i < 6; ir para 2
2. m(1) = 1, continuar em 3
3. R ‹ 011011 + 110110 = 010001, c = 1
4. (R r) ‹ desl.direita(1 010001 000000) = (101000 100000)
5. i ‹ 2; i < 6; ir para 2
2. m(2) = 0, c = 0 e ir para 4
4. (R r) ‹ desl.direita( 0 101000 100000) = (010100 010000)
5. i ‹ 3; i < 6; ir para 2
2. m(3) = 0, c = 0 e ir para 4
4. (R r) ‹ desl.direita(0 010100 010000) = (001010 001000)
5. i ‹ 4; i < 6; ir para 2
2. m(4) = 1, continuar em 3
3. R ‹ 001010 + 110110 = 000000, c= 1
4. (R r) ‹ desl.direita(1 000000 001000) = (100000 000100)
5. i ‹ 5; i < 6; ir para 2
6-4
2. m(5) = 1, continuar em 3
3. R ‹ 100000 + 110110 = 010110, c = 1
4. (R r) ‹ desl.direita(1 010110 000100) = (101011 000010)
5. i ‹ 6; fim. Resultado = 101011000010
O método pode ser melhorado ainda mais. Basta observar-se os seguintes pontos:
1. A rigor, ‘r’ não necessita ser inicializado com zeros. (No exemplo anterior, basta
substituir o ‘000000’ inicial de ‘r’ por ‘xxxxxx’)
2. Uma vez analisado, um bit do multiplicador não será mais utilizado (não influencia
mais no resultado) e pode ser descartado.
3. Considerando-se o item (2), para facilitar a análise dos bits do multiplicador, este
também pode ser deslocadopara a direita no passo 4. Assim, a análise será sempre no
bit menos significativo do multiplicador.
4. Desta maneira, a variável ‘i’ somente tem a função de controlar que o laço seja
executado ‘n’ vezes. Assim, ao invés de contar para cima de zero até ‘n’, pode-se
também contar para baixo de ‘n’ até zero (Observe-se que um teste de zero é bem
simples de ser realizado em um computador).
O algoritmo modificado em função destas observações pode ser visto a seguir. Sejam ‘m’,
‘M’, ‘R’, ‘r’, ‘n’ e ‘c’ definidos como anteriormente.
1. Início: i ‹ ‘n’, R ‹ 0
2. Deslocar m para a direita, juntamente com o carry. Note-se que o bit menos
significativo de m é levado para o carry:
( m c ) ‹ desl.direita( m )
Se c = 0, ir para 4.
3. Somar M a R (R ‹ R + M), c ‹ vai-um
4. Deslocar os ‘2n’ bits do resultado para direita, usando o ‘vai-um’ da soma
anterior como novo bit mais significativo do resultado (se não houve soma, usa-
se ‘0’ devido ao passo 2):
( R r ) ‹ desl.direita( c R r )
5. Decrementar ‘i’ de uma unidade (i ‹ i – 1)
Se ‘i’ não for zero, ir para 2. Senão, terminar. Resultado em (R r)
O resultado é expresso em ‘2n’ bits. Caso seja desejado um resultado em somente ‘n’ bits,
deve-se truncar os ‘n’ bits mais significativos. Neste caso, entretanto, deve-se testar por um
possível estouro de representação:
• Se os números forem representados como inteiros positivos, a truncagem é realizada
com sucesso (não há estouro) caso os ‘n’ bits mais significativos sejam todos iguais a
zero.
• Se os números forem representados como inteiros em complemento de dois (mas
positivos), a truncagem é realizada com sucesso (não há estouro) caso os ‘n+1’ bits
mas significativos sejam todos zero. Ou seja, os ‘n’ bits mais significativos devem ser
zeros para poderem ser desprezados, e o bit de sinal dos ‘n’ bits restantes deve ser zero
para o resultado ser positivo.
Para se adaptar às instruções de deslocamento para a direita do Ahmes, o algoritmo deve ser
um pouco modificado. No passo 2, deve ser usada a instrução de SHR (bit mais
significativo recebe zero, e o bit menos significativo vai para o carry). No passo 4, o
deslocamento conjunto de c, R e r deve ser desdobrado em duas instruções de ROR (bit mais
significativo recebe o valor atual do carry, e o bit menos significativo vai para o carry). Com
isto, o algoritmo fica:
6-5
1. Início: i ‹ ‘n’, R ‹ 0
2. Deslocar ‘m’ para direita (o bit menos significativo vai para o carry). Se o carry
for zero (c=0), ir para 4.
3. Somar M a R (R ‹ R + M), c ‹ vai-um
4. Deslocar os ‘2n’ bits do resultado para direita, usando o ‘c’ como novo bit mais
significativo do resultado: ( R m ) ‹ desl.direita( c R m )
4.1. Deslocar R para direita (carry recebe o bit menos significativo).
4.2. Deslocar r para direita (carry torna-se o novo bit mais significativo).
5. Decrementar ‘i’ de uma unidade (i ‹ i – 1)
Se ‘i’ não for zero, ir para 2. Senão, terminar. Resultado em (R m).
Para a implementação do algoritmo acima, assume-se o seguinte mapeamento de memória
para as variáveis e constantes:
multiplicando M: endereço 128 constante 0: endereço 134
multiplicador m: endereço 129 constante 1: endereço 135
resultado R: endereço 130 constante 8: endereço 136
resultado r: endereço 131
contador: endereço 132
multiplicador deslocado: endereço 133
Endereço Instrução Comentários
0 LDA 136
2 STA 132 Inicializa contador com ‘n’ (oito no caso)
4 LDA 134
6 STA 130 Inicializa R com zero
8 LDA 129
10 STA 133 Inicializa multiplicador com m
12 LDA 133 Início do laço: Carrega multiplicador em AC
14 SHR Desloca m; carry recebe o bit menos significativo
15 STA 133 Salva o multiplicador
17 JNC 25 Se não houve carry, vai para o deslocamento
19 LDA 130 Carrega R em AC
21 ADD 128 Soma R + M; resultado parcial no acumulador
23 STA 130 Salva o resultado parcial
25 LDA 130 Carrega resultado parcial (bits mais significativos) em AC
27 ROR Desloca para direita com carry
28 STA 130 Salva o resultado deslocado
30 LDA 131 Carrega resultado parcial (bits menos significativos) em AC
32 ROR Desloca para direita com carry
33 STA 131 Salva o resultado deslocado
35 LDA 132 Carrega o contador em AC
37 SUB 135 Decrementa de um
39 STA 132 Salva o contador
41 JNZ 12 Se não for zero, executa mais uma vez o laço
43 HLT Fim; resultado em R e m
Esta implementação pode ser otimizada, se os seguintes itens forem observados:
1. Depois do teste do carry (instrução JNC, no endereço 17), os dois ramos a serem
seguidos (endereços 25 e 19) iniciam com a mesma instrução (LDA 130).
2. Como a instrução LDA não altera o carry, ela pode ser deslocada para antes do teste
do carry. Com isto, em vez de duas instruções de LDA, usa-se apenas uma.
3. Como após a soma sobre R (endereços 19 a 23) segue-se o deslocamento de R
(endereços 25 a 28), pode-se eliminar também a instrução STA 130 do endereço 23.
Assim, a implementação fica (mantendo-se o mesmo mapeamento de variáveis e constantes):
6-6
Endereço Instrução Comentários
0 LDA 136
2 STA 132 Inicializa contador com ‘n’ (oito no caso)
4 LDA 134
6 STA 130 Inicializa R com zero
8 LDA 129
10 STA 133 Inicializa multiplicador com m
12 LDA 133 Início do laço: Carrega multiplicador em AC
14 SHR Desloca m; carry recebe o bit menos significativo
15 STA 133 Salva o multiplicador
17 LDA 130 Carrega resultado parcial (bits mais significativos) em AC
19 JNC 23 Se não houve carry (no SHR), vai para o deslocamento
21 ADD 128 Soma R + M; resultado parcial no acumulador
23 ROR Desloca R para direita com carry
24 STA 130 Salva o resultado deslocado
26 LDA 131 Carrega resultado parcial (bits menos significativos) em AC
28 ROR Desloca para direita com carry
29 STA 131 Salva o resultado deslocado
31 LDA 132 Carrega o contador em AC
33 SUB 135 Decrementa de um
35 STA 132 Salva o contador
37 JNZ 12 Se não for zero, executa mais uma vez o laço
39 HLT Fim; resultado em R e r
Uma otimização em termos de variáveis pode ser tentada, observando-se que:
1. Os bits do multiplicador são analisado da direita para esquerda. Isto é realizado
trazendo-se os seus bits para os bits menos significativos. Com isto os bits mais
significativos vão sendo liberados, um de cada vez.
2. Os bits menos significativos do resultado parcial vão sendo deslocados para ‘r’ pela
esquerda, ou seja, os bits são ocupados da esquerda para a direita, um de cada vez.
3. Assim, a medida que os bits menos significativos de ‘m’ vão sendo analisados, os
bits mais significativos de ‘r’ vão sendo formados. Assim, pode-se utilizar a mesma
palavra de memória (ou variável) para ‘r’ e ‘m’.
Com estas observações, pode-se desenvolver o método final para a multiplicação de dois
números binários, representados como inteiros positivos (este método vale também para
números positivos em complemento de dois). Sejam ‘m’, ‘M’, ‘R’ e ‘n’ definidos como
anteriormente. A variável ‘i’ tem a função de controlar que o laço seja executado ‘n’ vezes
(de ‘n’ até zero). A variável ‘r’ não é mais utilizada; sua função é realizada por ‘m’.
O algoritmo deve ser modificado, para se adaptar ao duplo uso de ‘m’ e ‘r’. A variável ‘m’ é
deslocada no início do laço, e ‘r’ é deslocada somente no fim. Na implementação abaixo,
optou-se por deslocar ‘m’ no início da laço, e somente ajustar o bit mais significativo de ‘r’
através de uma instrução de OR e uma máscara adequada (constante 128). Com isto, o
algoritmo fica:
1. Início: i ‹ ‘n’, R ‹ 0
2. Deslocar ‘m’ para direita (o bit menos significativo vai para o carry). Se o carry
for zero (c=0), ir para 4.
3. Somar M a R (R ‹ R + M), c ‹ vai-um
4. Deslocar os ‘2n’ bits do resultado para direita, usando o ‘c’ como novo bit mais
significativo do resultado: ( R m ) ‹ desl.direita( c R m )
4.1. Deslocar R para direita (carry recebe o bit menos significativo).
4.2. Testar o carry (que contem o bit menos significativo de R). Se for zero, não
há nadapara fazer (o bit mais significativo de m já é zero, devido ao passo 2). Se
for um, ligar o bit mais significativo de m.
6-7
5. Decrementar ‘i’ de uma unidade (i ‹ i – 1)
Se ‘i’ não for zero, ir para 2. Senão, terminar. Resultado em (R m).
Para a implementação do algoritmo acima, assume-se o mesmo mapeamento de memória dos
algoritmos anteriores, mas adaptado para este último algoritmo.
multiplicando M: endereço 128 constante 0: endereço 134
multiplicador m: endereço 129 constante 1: endereço 135
resultado R: endereço 130 constante 8: endereço 136
resultado r: endereço 131 constante 128: endereço 137
contador: endereço 132
Endereço Instrução Comentários
0 LDA 136
2 STA 132 Inicializa contador com ‘n’ (oito no caso)
4 LDA 134
6 STA 130 Inicializa R com zero
8 LDA 129
10 STA 131 Inicializa multiplicador com m
12 LDA 131 Início do laço: Carrega multiplicador em AC
14 SHR Desloca m; carry recebe o bit menos significativo
15 STA 131 Salva o multiplicador
17 LDA 130 Carrega resultado parcial (bits mais significativos) em AC
19 JNC 23 Se não houve carry (no SHR), vai para o deslocamento
21 ADD 128 Soma R + M; resultado parcial no acumulador
23 ROR Desloca R para direita; carry recebe bit menos significativo
24 STA 130 Salva o resultado deslocado
26 JNC 34 Se carry é zero, bits menos significativos (m) estão OK
28 LDA 131 Carrega resultado parcial (bits menos significativos) em AC
30 OR 137 Liga o bit mais significativo do resultado (m)
32 STA 131 Salva o resultado deslocado
34 LDA 132 Carrega o contador em AC
36 SUB 135 Decrementa de um
38 STA 132 Salva o contador
40 JNZ 12 Se não for zero, executa mais uma vez o laço
42 HLT Fim; resultado em R e m
6.2 Multiplicação binária (números em complemento de dois)
A multiplicação de números com sinal, em complemento de dois, usa o mesmo método
básico, com três modificações (duas no método e uma na realização da truncagem para ‘n’
bits):
1. Repete-se ‘n–1’ vezes o teste de bit, soma condicional e deslocamento. Na última
passagem do laço (na n-ésima vez), executa-se uma subtração condicional no lugar de
uma soma. Isto ocorre porque, em complemento de dois, o bit mais significativo
(sinal) tem peso negativo.
2. No deslocamento para a direita, deve-se agora manter (ou corrigir) o sinal do
resultado intermediário. Para isto, não se desloca mais com o vai-um da soma (ou
zero). Devem ser observadas as regras:
•se não houve soma (ou subtração) condicional anterior, desloca-se para a direita
duplicando-se o bit de sinal, isto é, o bit de sinal é deslocado para a direita, e o
novo bit de sinal é igual ao anterior.
•se houve soma (ou subtração) anterior, mas não ocorreu estouro, desloca-se para
a direita duplicando-se o bit de sinal.
•se houve soma (ou subtração) anterior, e ocorreu estouro, deslocam-se todos os
bits para a direita (inclusive o bit de sinal), e o novo bit de sinal é o inverso do
6-8
sinal anterior. Com isto corrige-se o erro na representação do resultado
introduzido pelo estouro.
3. Na truncagem para ‘n’ bits, deve-se observar que ela é agora possível em dois casos:
•Se os ‘n+1’ bits mais significativos forem zeros. Neste caso, tem-se um número
positivo em ‘2n’ bits que pode ser representado em ‘n’ bits, sem estouro.
•Se os ‘n+1’ bits mais significativos forem todos uns. Neste caso, tem-se um
número negativo em ‘2n’ bits que pode ser representado em ‘n’ bits, sem
estouro.
Nos demais casos, não é possível truncar o resultado para ‘n’ bits sem que haja
estouro de representação.
A implementação necessita de um teste de overflow após a soma, o que já está presente no
Ahmes. Dependendo do sinal do resultado parcial e do overflow, tem-se quatro casos a
tratar:
1. Resultado positivo, sem overflow (N=0, V=0). Neste caso, basta deslocar o resultado
através de uma instrução de SHR (que automaticamente coloca um zero no bit mais
significativo, mantendo assim o sinal).
2. Resultado positivo, com overflow (N=0, V=1). Neste caso, desloca-se o resultado
através de uma instrução de SHR e depois realiza-se um OR com a máscara binária
10000000 (decimal 128), para tornar o resultado negativo.
3. Resultado negativo, sem overflow (N=1, V=0). Este caso é o mesmo do item (2)
acima. Deve-se deslocar o resultado com um SHR e depois ligar o bit de sinal com um
OR com a máscara binária 10000000.
4. Resultado negativo, com overflow (N=1, V=1). Neste caso, como no caso (1) acima,
basta deslocar o resultado através de uma instrução de SHR (que coloca um zero no
bit mais significativo, tornando assim o resultado positivo).
Estes quatro casos referem-se simplesmente ao deslocamento dos bits mais significativos do
resultado. Considerando-se a necessidade de identificar o caso e tratá-lo adequadamente, e
repetir a análise separadamente para o último passo (que utiliza subtração condicional em vez
de soma), a programação deste algoritmo em Ahmes seria bem extensa e complexa. Para o
Ahmes, seria mais simples converter os operandos para números positivos, multiplicá-los e
depois ajustar o sinal o resultado de acordo com os sinais dos operandos originais.
Um outro método para multiplicação binária para números em complemento de dois foi
desenvolvido por Booth, e é mais rápido que os métodos descritos acima. Este algoritmo
pode ser encontrado no livro Computer Architecture and Organization, de John P. Hayes, na
seção 3.3.2.
6.3 Divisão binária (números inteiros positivos)
Em qualquer sistema de numeração, a divisão é a operação inversa da multiplicação, ou seja,
seu resultado (quociente) indica quantas vezes podemos subtrair um número (divisor) de
outro (dividendo) de forma que ainda reste um número positivo ou zero (resto). Na divisão
em decimal, realizam-se exatamente os passos contrários da multiplicação. Os dígitos do
resultado são calculados da esquerda para direita, e a cada passo determina-se um dígito do
quociente:
7749 ÷ 63 
 –63 123
144 (7749 – 6300 = 1449)
 –126 
189 (1449 – 1260 = 189)
 –189 
0 (189 – 189 = 0)
6-9
Note-se que, como na multiplicação, o peso de cada casa é assumido implicitamente, e os
zeros respectivos não são escritos. Assim, no lugar de 6300 (63 x 1 x 100) anota-se
simplesmente 63 (63 x 1); no lugar de 1260 (63 x 2 x 10) escreve-se 126 (63 x 2). A
divisão apresenta uma dificuldade adicional para sua realização pelo método esboçado acima:
a necessidade de “estimar” o dígito que deve ser multiplicado pelo divisor para obter a maior
parcela possível de ser subtraída do dividendo.
Na divisão binária, utiliza-se exatamente o mesmo método, mas o processo de “adivinhação”
se torna bem mais fácil: só é necessário verificar se o divisor pode ser subtraído dos dígitos
mais significativos do dividendo (bit = 1) ou não (bit = 0).
1 0 1 0 1 1 0 0 0 0 1 0 ÷ 1 1 0 0 1 1 
 – 1 1 0 0 1 1 1 1 0 1 1 0
1 0 0 0 1 1 0
 – 1 1 0 0 1 1 
0 1 0 0 1 1 0
1 0 0 1 1 0 0
 – 1 1 0 0 1 1 
0 1 1 0 0 1 1
 – 1 1 0 0 1 1 
0 0 0 0 0 0
0 0 0 0 0 0
Note-se que, como no sistema decimal, depois de cada subtração (ou tentativa mal sucedida
de subtração, se o dígito calculado para o quociente for zero) um novo dígito do dividendo é
incorporado à análise, isto é, um novo dígito do dividendo é “baixado” para o resultado da
subtração. E, também como no sistema decimal, o número de bits do dividendo que
participam da primeira análise é escolhido de tal forma que formem um número maior que o
divisor, isto é, que a primeira subtração seja possível.
Com um dividendo de ‘m’ bits e um divisor de ‘n’ bits obtém-se um quociente de ‘m–n’ bits
e um resto de ‘n’ bits. A divisão em um computador, sendo a operaçãoinversa da
multiplicação, opera com um dividendo de ‘2n’ bits, um divisor de ‘n’ bits e fornece
quociente e resto em ‘n’ bits. Ao contrário da multiplicação, entretanto, onde o resultado
sempre é representável sem estouro, na divisão o quociente pode não ser representável em
‘n’ bits. Nestes casos sinaliza-se estouro de representação. Nos casos em que o dividendo
tem somente ‘n’ bits, ele deve ser inicialmente expandido para ‘2n’ bits, incluindo-se ‘n’
zeros à esquerda do dividendo.
Para divisão de dois números representados como inteiros positivos usa-se o método abaixo,
onde o dividendo ‘D’ tem ‘2n’ bits e o divisor ‘v’ tem ‘n’ bits. Note-se que, nesta
representação não existem números negativos. Assim, um teste comparativo deve ser feito
para verificar se a subtração é possível, ou seja, se o resultado será um número positivo.
Observe-se também que sua aplicação restringe-se aos números naturais sem o ‘zero’ . A
inclusão do ‘zero’, obrigaria ao teste do valor do divisor, abortando a operação se esta for
uma tentativa de divisão por zero.
1. Início: formar ‘r’ com os ‘n+1’ bits mais significativos do dividendo ‘D’, i ‹ ‘n’.
2. Se r ‡ v, então subtrair r ‹ r–v e colocar 1 no bit menos significativo de q
(quociente). Senão, somente colocar 0 no bit menos significativo de ‘q’. Obs: neste
passo, usar somente ‘n’ bits para representar ‘r’.
3. Decrementar i (i ‹ i–1). Se i=0, encerrar. O resto está em ‘r’ e o quociente em ‘q’.
4. Deslocar ‘r’ para esquerda, mantendo o bit mais significativo (ou seja, representar
‘r’ com ‘n+1’ bits). Como novo bit menos significativo, utilizar o bit seguinte do
dividendo original (“baixar um bit”). Deslocar ‘q’ também para a esquerda. Ir para
o passo 2.
Exemplo: sejam D = 101011000010 e v = 110011. Então tem-se:
6-10
1. r ‹ 1010110, i ‹ 6
2. r ‡ v (1010110 ‡ 110011). Então r ‹ 1010110 – 110011 = 100011 e q ‹ 1
3. i ‹ 5
4. r ‹ 1000110, q ‹ 1x
2. r ‡ v (1000110 ‡ 110011). Então r ‹ 1000110 – 110011 = 010011 e q ‹ 11
3. i ‹ 4
4. r ‹ 0100110, q ‹ 11x
2. r < v (0100110 < 110011). Então r ‹ 100110 e q ‹ 110
3. i ‹ 3
4. r ‹ 1001100, q ‹ 110x
2. r ‡ v (1001100 ‡ 110011). Então r ‹ 1001100 – 110011 = 011001 e q ‹ 1101
3. i ‹ 2
4. r ‹ 0110011, q ‹ 1101x
2. r ‡ v (0110011 ‡ 110011). Então r ‹ 0110011 – 110011 = 000000 e q ‹ 11011
3. i ‹ 1
4. r ‹ 0000000, q ‹ 11011x
2. r < v (0000000 < 110011). Então r ‹ 000000 e q ‹ 110110
3. i ‹ 0, encerrar. Quociente = 110110 e resto = 0
Para alguns operandos, pode ocorrer que quando for executado o passo 2, na primeira vez, o
resultado da operação r ‹ r–v seja maior do que ‘v’ (ou até mesmo igual a ‘v’). Nestes
casos, o algoritmo não é adequado para realização da operação (portanto, a divisão não
poderá ser realizada por este método: será necessário escolher algum outro). Para o uso
adequado deste algoritmo, é interessante incluir uma observação no passo 2 de verificação do
resultado da operação r ‹ r–v. Se após esta operação obter-se r ‡ v, então deve-se abortar a
operação, pois o quociente exigiria mais de ‘n’ bits para ser representado.
A situação explicada acima é exemplificada com a divisão de 11010100 por 1011. Para este
exemplo, D = 11010100 e v = 1011. Então tem-se:
1. r ‹ 11010, i ‹ 4
2. r ‡ v (11010 ‡ 1011). Então r ‹ 11010 – 1011 = 1111 e q ‹ 1
Neste passo, se obtém um valor de ‘r’ que é maior do que o divisor (o que não faz sentido).
O prosseguimento da operação pelo algoritmo faria com que se obtenha uma resposta
incorreta.
Como poderia ser corrigido o algoritmo sem modificá-lo demasiadamente? Se, para iniciar a
operação, utilizar-se apenas n bits do dividendo (D), o problema se resolve a nível do passo
2. Mas agora será necessária uma interação a mais (é preciso “baixar” mais um bit de D),
então i deve ser aumentado em uma unidade. Entretanto esta é uma solução para este caso e
não universal. Experimente mudar o divisor para 0101 e observe o que ocorre. O tipo de
análise e a visão humana sobre as variáveis não são facilmente “transportáveis” para o
computador, o que vai exigir a alteração do algoritmo para implementação na máquina.
Com isto, o algoritmo fica:
1. Início: Se v for zero, terminar indicando erro de divisão por zero. Senão, calcular D
– v. Se carry=1 (borrow=0), então D ‡ v e terminar indicando estouro. Se não,
então a divisão pode ser realizada.
6-11
i ‹ ‘n’. Formar ‘r’ com os ‘n+1’ bits mais significativos do dividendo.
2. Se r ‡ v, então subtrair r ‹ r–v e colocar 1 no bit menos significativo de q
(quociente). Senão, somente colocar 0 no bit menos significativo de ‘q’. Obs: neste
passo, usar somente ‘n’ bits para representar o resultado ‘r’.
3. Decrementar i (i ‹ i–1). Se i=0, encerrar. O resto está em ‘r’ e o quociente em ‘q’.
4. Deslocar ‘r’ para esquerda, mantendo o bit mais significativo (ou seja, representar
‘r’ com ‘n+1’ bits). Como novo bit menos significativo, utilizar o bit seguinte do
dividendo original (“baixar um bit”). Deslocar ‘q’ também para a esquerda. Ir para
o passo 2.
O algoritmo requer que se trabalhe com os ‘n+1’ bits mais significativos do dividendo. Isto
pode ser implementado realizando-se um deslocamento para a esquerda do dividendo, de
forma que o carry contenha o bit mais significativo e ‘D’ contenha os ‘n’ bits seguintes.
Assim, a comparação é entre ‘r’ (carry e D) e ‘v’. Se o carry for um, então garantidamente
‘r’ > ‘v’. Se o carry for zero, então calcula-se ‘D’–‘v’. Se o borrow desta operação for zero
(borrow=0), então ‘r’ ‡ ‘v’. Se o borrow for um (borrow=1) então ‘r‘<‘v‘.
Com estas considerações, o algoritmo fica:
1. Início: Se v for zero, terminar indicando erro de divisão por zero. Senão, verificar
se D ‡ v. Se sim, ocorrerá estouro no quociente. Neste caso, terminar indicando
estouro. Se não, então a divisão pode ser realizada.
2. Início: i ‹ n, q ‹ 0.
3. Deslocar o quociente q para esquerda, preparando-o para receber o novo bit menos
significativo. Deslocar D e d para esquerda (bit mais significativo de D vai para o
carry). Testar D e carry contra v. Se carry =1, então D > v. Senão, calcular D – v.
Se houver borrow, então D<v. Senão, D ‡ v. No caso de D ‡ v, subtrair D ‹ D–v e
colocar 1 no bit menos significativo de q (quociente). Senão, deixar D inalterado e
colocar 0 no bit menos significativo de q (como o deslocamento para esquerda já
inseriu um zero, basta deixar q inalterado).
4. Decrementar i (i ‹ i–1). Se i=0, encerrar. O resto está em ‘D’ e o quociente em
‘q’. Senão, ir para o passo 3.
No algoritmo para o AHMES, assume-se que o dividendo esteja nos endereços 128 (D - bits
mais significativos) e 129 (d - bits menos significativos), o divisor v no endereço 130, o
quociente q deve ser colocado em 131 e o resto r em 132. O estado da divisão é indicado na
posição 133 (-1 indica estouro na divisão, 0 indica divisão por zero e 1 indica divisão
normal). Para contador será utilizada a posição 134.
Para as constantes, são utilizadas as seguintes posições: 135 para zero, 136 para um, 137
para menos um (255) e 138 para oito.
Para deixar os valores de ‘D’ e ‘d’ inalterados, os seus valores serão copiados para as
posições 139 e 140, respectivamente. Sobre estas posições é que serão efetuados os
deslocamentos.
Endereço Instrução Comentários
0 LDA 130 Carrega o divisor
2 JZ 77 Se for zero, termina
4 LDA 128 Carrega D em A
6 SUB 130 Calcula D – v
8 JNB 81 Se borrow=0, então D ‡ v, e irá ocorrer estouro
10 LDA 128 Tudo bem. Divisão pode ser realizada
12 STA 139 Salva D em endereço temporário
14 LDA 129 Carrega d
16 STA 140 Salva d em endereço temporário
18 LDA 138 Obtém a constante 8
6-12
20 STA 134 Inicializa contador com ‘n’ (8 no caso)
22 LDA 135 Obtém a constante zero
24 STA 131 Inicializa q com zero
26 LDA 131 Carrega q
28 SHL Desloca q para esquerda
29 STA 131 Salva q
31 LDA 140 Carrega d
33 SHL Desloca d para esquerda (carry recebebit mais significativo)
34 STA 140 Salva d
36 LDA 139 Carrega D
38 ROL Desloca D para esquerda (com carry)
39 STA 139 Salva D
41 JC 49 Testa o carry (antigo bit mais significativo de D)
43 LDA 139 Carry de D = 0, carrega D
45 SUB 130 Testa se D – v
47 JB 61 Testa o borrow; se 1, então D < v, nada a fazer
49 LDA 139 Borrow=0, então D > v
51 SUB 130 Atualiza D com D–v
53 STA 139 Atualiza D
55 LDA 131 Carrega q
57 OR 136 Coloca bit do quociente em 1
59 STA 131 Salva q
61 LDA 134 Carrega contador
63 SUB 136 Decrementa contador de laço
65 STA 134 Salva contador
67 JNZ 26 Se não for zero, termina
69 LDA 139 Obtém o D final
71 STA 132 Salva como resto
73 LDA 136 Sinaliza fim normal
75 JMP 83
77 LDA 135 Sinaliza divisão por zero
79 JMP 83
81 LDA 137 Sinaliza estouro na divisão
83 STA 133 Armazena indicador de estado
85 HLT Fim
O algoritmo acima pode ser otimizado observando-se que:
1. Enquanto os bits de ‘d’ vão sendo deslocados para a esquerda, os bits de ‘q’ vão
sendo formados a partir da direita. Assim, de maneira análoga ao caso da
multiplicação, para ‘d’ e ‘q’ pode ser utilizada uma só variável e em consequencia
uma só posição de memória. Assim, os endereços 140 e 131 são reunidos,
eliminado-se o 140.
2. Da variável ‘D’ vão sendo realizadas subtrações sucessivas, e no final do algoritmo
o ‘D’ final é o resto. Assim, para ‘D’ e ‘r’ pode-se utilizar somente uma variável.
Assim, dos endereços 139 e 132 elimina-se a necessidade do 139.
Com estas considerações, o algoritmo fica:
1. Início: Se v for zero, terminar indicando erro de divisão por zero. Senão, verificar
se D ‡ v. Se sim, ocorrerá estouro no quociente. Neste caso, terminar indicando
estouro. Se não, então a divisão pode ser realizada.
2. Início: i ‹ n, q ‹ d, r ‹ D.
3. Deslocar r e q (ou seja, D e q) para esquerda (bit mais significativo de r vai para o
carry). Testar r e carry contra v. Se carry =1, então r > v. Senão, calcular r – v. Se
houver borrow, então r<v. Senão, r‡ v. No caso de r ‡ v, subtrair r ‹ r–v e colocar
1 no bit menos significativo de q. Senão, deixar D e q inalterados.
6-13
4. Decrementar i (i ‹ i–1). Se i=0, encerrar. O resto está em ‘r’ e o quociente em ‘q’.
Senão, ir para o passo 3.
No algoritmo para o AHMES, assume-se que o dividendo esteja nos endereços 128 (D - bits
mais significativos) e 129 (d - bits menos significativos), o divisor v no endereço 130, o
quociente q deve ser colocado em 131 e o resto r em 132. O estado da divisão é indicado na
posição 133 (-1 indica estouro na divisão, 0 indica divisão por zero e 1 indica divisão
normal). Para contador será utilizada a posição 134.
Para as constantes, são utilizadas as seguintes posições: 135 para zero, 136 para um, 137
para menos um (255) e 138 para oito.
Note-se que para ‘D’ temporário e ‘r’ é utilizada a mesma posição (132), assim como para
‘d’ temporário e o quociente ‘q’ é utilizada a mesma posição (131). A cópia de ‘D’ para ‘r’ é
feita no endereço 12 (STA 132), e a cópia de ‘d’para ‘q’ é feita na instrução do endereço 16
(STA 131).
Endereço Instrução Comentários
0 LDA 130 Carrega o divisor
2 JZ 64 Se for zero, termina
4 LDA 128 Carrega D em A
6 SUB 130 Calcula D – v
8 JNB 68 Se borrow=0, então D ‡ v, e irá ocorrer estouro
10 LDA 128 Tudo bem. Divisão pode ser realizada
12 STA 132 Salva D como o resto temporário (r)
14 LDA 129 Carrega d
16 STA 131 Salva d como quociente temporário (q)
18 LDA 138 Obtém a constante 8
20 STA 134 Inicializa contador com ‘n’ (8 no caso)
22 LDA 131 Carrega d (q)
24 SHL Desloca para esquerda (carry recebe bit mais significativo)
25 STA 131 Salva d (q)
27 LDA 132 Carrega D (r)
29 ROL Desloca para esquerda (com carry)
30 STA 132 Salva D (r)
32 JC 40 Testa o carry (antigo bit mais significativo de D(r))
34 LDA 132 Carry de r = 0, carrega r
36 SUB 130 Testa se r – v
38 JB 52 Testa o borrow; se 1, então r < v, nada a fazer
40 LDA 132 Borrow=0, então r > v
42 SUB 130 Calcula r–v
44 STA 132 Atualiza r
46 LDA 131 Carrega d (q)
48 OR 136 Coloca bit do quociente em 1
50 STA 131 Salva d (q)
52 LDA 134 Carrega contador
54 SUB 136 Decrementa contador de laço
56 STA 134 Salva contador
58 JNZ 22 Se não for zero, termina
60 LDA 136 Sinaliza fim normal
62 JMP 70
64 LDA 135 Sinaliza divisão por zero
66 JMP 70
68 LDA 137 Sinaliza estouro na divisão
70 STA 133 Armazena indicador de estado
72 HLT Fim
6-14
6.4 Divisão binária (números em complemento de dois, positivos)
Na representação em complemento de dois, é possível representar números negativos, e
assim o método discutido acima pode ser modificado. Não é mais necessário testar para
verificar se a subtração é possível. Simplesmente realiza-se a subtração e, se o resultado for
negativo, restaura-se o número original somando-se o divisor. Este é o método da “divisão
com restauração”.
Sejam ‘D’ o dividendo (com ‘2n’ bits) e ‘v’ o divisor (em ‘n’ bits). O quociente ‘q’ será
então representado por qn-1qn-2...q2q1q0 em ‘n’ bits. O algorimo calcula um bit qi de cada
vez, da esquerda para a direita (‘i’ variando de ‘n-1’ até zero). A cada passo ‘i’ o divisor,
deslocado ‘i’ bits para a esquerda (representado por 2iv), é comparado com o resto parcial ri
(inicialmente, rn-1 é formado pelos bits mais significativos do dividendo). Se 2iv for menor
que ri, o bit qi do quociente é colocado em 0. Se 2iv for maior (ou igual) que ri, o bit qi do
quociente é colocado em 0, e um novo resto parcial é calculado pela operação
ri-1 ‹ ri – qi2iv
Nos métodos normalmente utilizados, é mais conveniente deslocar o resto parcial para
esquerda em relação a um divisor fixo. Assim, o divisor permanece sempre ‘v’, e o resto
parcial deslocado para a esquerda é representado por 2ri. Neste caso, a equação acima é
equivalente a
ri-1 ‹ 2ri – qiv
Quando se realiza uma subtração tentativa, calcula-se ri-1 ‹ 2ri – v. Esta operação já calcula
o novo resto parcial ri-1 quando 2ri – v for positivo, isto é, quando qi = 1. Se entretanto 2ri –
v for negativo, tem-se qi = 0 e o novo resto parcial ri-1 será igual ao anterior, ou seja, 2ri.
Este resto ri-1 pode neste caso ser obtido somando-se ‘v’ de volta ao resultado da subtração.
Esta é a base do método da divisão com restauração. A cada passagem a operação
ri-1 ‹ 2ri – v
é realizada. Quando o resultado é negativo, uma adição restauradora é necessária:
ri-1 ‹ ri-1 + v
ri-1 ‹ (2ri – v) + v = 2ri
Se a probabilidade de qi = 1 for 1/2, então este método requer ‘n’ subtrações e uma média de
‘n/2’ somas. Para o algoritmo abaixo, sejam ‘D’ os ‘n’ bits mais significativos do dividendo,
‘d’ os ‘n’ bits menos significativos do dividendo, ‘v’ o divisor (em ‘n’ bits). Para ‘d’ e ‘q’
utiliza-se a mesma variável.
1. Início: Se v for zero, terminar indicando erro de divisão por zero. Senão, deslocar
(D d) para a esquerda: (D d) ‹ desl.esquerda(D d 0). Se D for maior ou igual a v,
ocorrerá estouro no quociente. Neste caso, terminar indicando estouro. Senão,
fazer r ‹ D, i ‹ ‘n’ e q ‹ d.
2. Subtrair r ‹ r–v. Se r resultante for positivo, colocar 1 no bit menos significativo
de q. Senão, colocar zero no bit menos significativo de q e restaurar r através da
soma r ‹ r+v.
3. Decrementar i (i ‹ i–1). Se i=0, encerrar. O resto está em ‘r’ e o quociente em ‘q’.
4. Deslocar (r q) para esquerda: (r q) ‹ desl.esquerda(r q 0). Ir para o passo 2.
Na adaptação para o Ahmes, assume-se que o dividendo esteja nos endereços 128 (D - bits
mais significativos) e 129 (d - bits menos significativos), o divisor v no endereço 130, o
quociente q deve ser colocado em 131 e o resto r em 132. O estado da divisão é indicado na
posição 133 (-1 indica estouro na divisão, 0 indica divisão por zero e 1 indica divisão
6-15
normal). Para contador será utilizada a posição 134. Para as constantes, são utilizadas as
seguintes posições: 135 para zero, 136 para um, 137 para menos um (255) e 138 para oito.
Note-se quepara d e q e para r e D são utilizadas as mesmas palavras de memória (131 e
132, respectivamente), o que pode ser visto nas instruções dos endereços 7 e 12.
Endereço Instrução Comentários
0 LDA 130 Carrega o divisor
2 JZ 60 Se for zero, termina
4 LDA 129 Carrega d em A
6 SHL Desloca para esquerda, bit mais significativo vai para carry
7 STA 131 Salva d como q (quociente temporário)
9 LDA 128 Carrega D em A
11 ROL Desloca para esquerda
12 STA 132 Salva D como r (resto temporário)
14 SUB 130 Calcula D – v
16 JP 64 Se D ‡ v, irá ocorrer estouro
18 LDA 138 Tudo bem ( D < v ). Divisão pode ser realizada
20 STA 134 Inicializa contador com ‘n’ (8 no caso)
22 LDA 132 Início do laço. Obtém r
24 SUB 130 Calcula r – v
26 JN 36 Se negativo, nada a fazer (não salva r)
28 STA 132 Se positivo, atualiza r
30 LDA 131 Carrega q
32 OR 136 Coloca bit do quociente em 1
34 STA 131 Salva q
36 LDA 134 Carrega contador
38 SUB 136 Decrementa contador de laço
40 STA 134 Salva contador
42 JZ 56 Se for zero, termina normalmente
44 LDA 131 Carrega q
46 SHL Desloca para esquerda, bit mais significativo vai para carry
47 STA 131 Salva q
49 LDA 132 Carrega r
51 ROL Desloca para esquerda
52 STA 132 Salva r
54 JMP 22 Volta para início do laço
56 LDA 136 Sinaliza fim normal
58 JMP 66
60 LDA 135 Sinaliza divisão por zero
62 JMP 66
64 LDA 137 Sinaliza estouro na divisão
66 STA 133 Armazena indicador de estado
68 HLT Fim
Note-se que o programa está otimizado no que se refere à restauração do ‘r’. A subtração é
realizada (posições 22 e 24) e testada (posição 26). No instante do teste, o resultado ‘r–v’
está no acumulador, e a variável ‘r’ na memória ainda não foi atualizada. Assim, a
“restauração de r” é realizada simplesmente não salvando o resultado do acumulador, e a
operação ‘r ‹ r–v’ é realizada salvando-se o acumulador (posição 28).
Uma técnica um pouco diversa da descrita acima pode ser empregada para eliminar a
necessidade de realizar a soma restauradora. Esta técnica é baseada no fato de uma
restauração da forma
ri ‹ ri + v
é seguida no próximo passo por uma subtração da forma:
ri-1 ‹ 2ri – v
6-16
Reunindo-se as duas equações tem-se
ri-1 ‹ 2(ri + v) – v = 2ri + 2v – v
ou seja,
ri-1 ‹ 2ri + v
Assim, quando qi = 1, que indica um valor positivo para ri, ri-1 é calculado por subtração do
divisor: ri-1 ‹ 2ri – v. Por outro lado, quando qi = 0, r i-1 é calculado por uma simples
soma: ri-1 ‹ 2ri + v. Assim, o cálculo de cada um dos bits do quociente requer uma soma
ou uma subtração, mas não ambas. Assim, este método, denominado de divisão sem
restauração, necessita de ‘n’ somas e subtrações, enquanto que o método da divisão com
restauração requer uma média de 3n/2 somas e subtrações.
Para o algoritmo abaixo, sejam ‘r’ os ‘n’ bits mais significativos do dividendo, ‘d’ os ‘n’
bits menos significativos do dividendo, ‘v’ o divisor (em ‘n’ bits). Para controlar se a
próxima operação será uma soma ou subtração, usa-se um elemento auxiliar ‘aux’,
inicializado para começar-se com uma subtração.
1. Início: Se v for zero, terminar indicando erro de divisão por zero. Senão, deslocar
(D d) para a esquerda: (D d) ‹ desl.esquerda(D d 0). Se D for maior ou igual a v,
ocorrerá estouro no quociente. Neste caso, terminar indicando estouro. Senão,
fazer r ‹ D, i ‹ ‘n’ e aux ‹ 1.
2. Se aux=1, calcular r ‹ r–v. Senão, calcular r ‹ r+v. Se o ‘r’ resultante for
positivo, então colocar 1 no bit menos significativo de q e fazer aux ‹ 1. Se o ‘r’
resultante for negativo, colocar 0 no bit menos significativo de q e fazer aux ‹ 0.
3. Decrementar i (i ‹ i–1). Se i=0, ir para 5.
4. Deslocar (r d) para esquerda: (r d) ‹ desl.esquerda(r d 0). Deslocar q para a
esquerda: q ‹ desl.esquerda(q 0). Ir para o passo 2.
5. Se r<0, então r ‹ r+v. Encerrar. O resto está em ‘r’ e o quociente em ‘q’
Como pode ser visto no passo 2, se o dividendo após uma subtração ficar negativo, ele não é
restaurado, mas sim no próximo passo soma-se o divisor (ao invés de subtrair). Isto é
controlado pelo “flag” aux. Assim, sempre que a operação anterior produzir um dividendo
positivo, a próxima operação é uma subtração; senão, se o dividendo for negativo, a próxima
operação é uma soma. Este método necessita, entretanto, corrigir o resto, como indicado no
passo 5.
Na adaptação para o Ahmes, assume-se que o dividendo esteja nos endereços 128 (D - bits
mais significativos) e 129 (d - bits menos significativos), o divisor v no endereço 130, o
quociente q deve ser colocado em 131 e o resto r em 132. O estado da divisão é indicado na
posição 133 (-1 indica estouro na divisão, 0 indica divisão por zero e 1 indica divisão
normal). Para contador será utilizada a posição 134. Para as constantes, são utilizadas as
seguintes posições: 135 para zero, 136 para um, 137 para menos um (255) e 138 para oito.
Para a variável ‘aux’ usa-se a posição 139.
Endereço Instrução Comentários
0 LDA 130 Carrega o divisor
2 JZ 92 Se for zero, termina
4 LDA 129 Carrega d em A
6 SHL Desloca para esquerda, bit mais significativo vai para carry
7 STA 131 Salva d como q (quociente temporário)
9 LDA 128 Carrega D em A
11 ROL Desloca para esquerda
12 STA 132 Salva D como r (resto temporário)
14 SUB 130 Calcula D – v
6-17
16 JP 96 Se D ‡ v, irá ocorrer estouro
18 LDA 138 Tudo bem ( D < v ). Divisão pode ser realizada
20 STA 134 Inicializa contador com ‘n’ (8 no caso)
22 LDA 136
24 STA 139 Inicializa aux com 1
26 LDA 139 Início do laço. Testa aux
28 JZ 38
30 LDA 132 Aux = 1
32 SUB 130 Calcula r – v
34 STA 132 Atualiza r
36 JMP 44
38 LDA 132 Aux = 0
40 ADD 130 Calcula r + v
42 STA 132 Atualiza r
44 JN 56 Testa o resultado da operação
46 LDA 131 Carrega q
48 OR 136 Coloca bit do quociente em 1
50 STA 131 Salva q
52 LDA 136 Faz aux=1 (próxima operação é uma subtração)
54 JMP 58
56 LDA 135 Faz aux=0 (próxima operação é uma soma)
58 STA 139 Atualiza variável aux
60 LDA 134 Carrega contador
62 SUB 136 Decrementa contador de laço
64 STA 134 Salva contador
66 JZ 80 Se for zero, termina normalmente
68 LDA 131 Carrega q
70 SHL Desloca para esquerda, bit mais significativo vai para carry
71 STA 131 Salva q
73 LDA 132 Carrega r
75 ROL Desloca para esquerda
76 STA 132 Salva r
78 JMP 26 Volta para início da laço
80 LDA 132 Fim do laço. Testa valor do resto
82 JP 88 Se for positivo, está correto
84 ADD 130 Se negativo, soma divisor ao resto
86 STA 132 Salva resto corrigido
88 LDA 136 Sinaliza fim normal
90 JMP 98
92 LDA 135 Sinaliza divisão por zero
94 JMP 98
96 LDA 137 Sinaliza estouro na divisão
98 STA 133 Armazena indicador de estado
100 HLT Fim
No lugar de corrigir o resto, alguns autores preferem realizar o laço ‘n–1’ vezes (e não ‘n’
vezes, como acima), e na última passagem forçar o bit menos significativo do quociente para
1. O resultado final sempre será algebricamente correto, no sentido que quociente vezes
divisor mais resto é igual ao dividendo, mas pode produzir “anomalias” como 21 ÷ 5 = 5 e
resta –4, ou então até mesmo 20 ÷ 5 = 5 e resta –5 (!). Mas 15 ÷ 5 = 3 e resta zero, assim
como 19 ÷ 5 = 3 e resta 4. Como o quociente sempre será impar (devido ao bit menos
significativo ser forçado para um), esta anomalia ocorre sempre que o quociente correto seria
um número par. A correção, entretanto, é fácil: sempre que o resto for negativo, basta
subtrair um do quociente e somar o divisor ao resto.
Exemplo de uso do método: seja a divisão de 000111000111 por 010001, ambos
interpretados como números em complemento de dois (note-se que ambos são positivos):
6-18
1. i ‹ 0, aux ‹ 1, r ‹ 000111, d ‹ 000111. Deslocando (r d) para esquerda,
resulta em r ‹ 001110, d ‹ 001110. Como r<v e v „ 0, a divisão pode prosseguir.
2. r ‹ 001110 – 010001 = 001110+ 101111 = 111101, q ‹ 0, aux ‹ 0
3. i ‹ 1; i < 6; ir para 4
4. r ‹ 111010, d ‹ 011100, q ‹ 0x
2. r ‹ 111010 + 010001 = 001011, q ‹ 01, aux ‹ 1
3. i‹ 2; i < 6; ir para 4
4. r ‹ 010110, d ‹ 111000, q ‹ 01x
2. r ‹ 010110 – 010001= 010110+ 101111 = 000101, q ‹ 011, aux ‹ 1
3. i ‹ 3; i < 6; ir para 4
4. r ‹ 001011, d ‹ 110000, q ‹ 011x
2. r ‹ 001011 – 010001= 001011+ 101111 = 111010, q ‹ 0110, aux ‹ 0
3. i ‹ 4; i < 6; ir para 4
4. r ‹ 110101, d ‹ 100000
2. r ‹ 110101 + 010001= 000110, q ‹ 01101, aux ‹ 1
3. i ‹ 5; i < 6; ir para 4
4. r ‹ 001101, d ‹ 000000, q ‹ 01101x
2. r ‹ 001101 – 010001= 001101+ 101111 = 111100, q ‹ 011010, aux ‹ 0
3. i ‹ 6; i ‡ 6; ir para 5
5. r ‹ 111100 + 010001 = 001101. Quociente = 011010 e resto = 001101. Ou seja,
dividindo-se 455 por 17 obtém-se 26 e resta 13.
Seja agora a divisão de 001011000010 por 010011, ambos em complemento de dois. Neste
caso, o passo um indica que r > v, ou seja, 010110 > 010011. Neste caso, a divisão não é
possível, pois o dividendo não é representável em seis bits (estouro de representação). Em
decimal, a divisão desejada seria de 706 por 19, o que resultaria em um quociente de 37, que
não é representável em complemento de dois em seis bits.
Na divisão de 001000010010 por 010011, o resultado obtido será 011011, com resto de
010001. Neste caso, o resto já é produzido correto, sem necessidade de correção no
passo 5.
6.5 Divisão binária (números em complemento de dois, positivos ou
negativos)
O método da divisão sem restauração pode ser generalizado para números inteiros positivos e
negativos. Para a divisão ser possível sem estouro, a comparação inicial requer que o valor
absoluto de ‘r’ seja menor que o valor absoluto de ‘v’. Se o sinais de dividendo e divisor
forem iguais, inicia-se com uma subtração; senão inicia-se com uma soma. Após cada
subtração (ou soma), comparam-se os sinais do divisor e do resultado. Se forem iguais, um
bit 1 é colocado no quociente, e a próxima operação é uma subtração. Se forem diferentes,
um bit 0 é adicionado ao quociente, e a próxima operação é uma soma. O bit final do
quociente é forçado para 1, independente do valor da análise dos sinais.
O resultado está algebricamente correto, no sentido do quociente ser igual ao divisor vezes o
quociente mais o resto. Entretanto, pode ocorrer que dividendo e resto tenha sinais
diferentes, assim como que o resto seja igual ao divisor. Para corrigir-se quociente e resto,
de forma que o resto seja sempre menor que o divisor e seu sinal igual ao do dividendo, o
seguinte procedimento é necessário:
6-19
• se o resto for zero, o resultado está correto.
• se o resto for diferente de zero, comparam-se os sinais do dividendo e do resto. Se
forem diferentes, então corrige-se o resultado:
• se dividendo e divisor tiverem os mesmos sinais, subtrai-se um do quociente o
soma-se o divisor ao resto para obter-se o resto real.
• se dividendo e divisor tiverem sinais diferentes, soma-se um ao quociente e
subtrai-se o divisor do resto para a obtenção do resto real.
• se o resto for diferente de zero, dividendo e resto forem ambos negativos, e o valor
absoluto do resto for igual ao valor absoluto do divisor, então o resto é zero e o
quociente deve ser corrigido. Se o divisor for negativo, soma-se um ao quociente, caso
contrário subtrai-se um.
6.6 Exercícios resolvidos
Atenção: para os exercícios a seguir todos os números sugeridos são inteiros positivos.
1. Multiplicar 1011 por 1101.
Empregando-se o algoritmo explicado na seção 4.1, tem-se o desenvolvimento apresentado a
seguir. As variáveis são: M = 1011 e m = 1101.
1. i ‹ 0, R ‹ 0, r ‹ 0, M ‹ 1011, m ‹ 1101.
2. m0 = 1, continuar em 3.
3. R ‹ 0 + 1011 = 1011; c = 0
4. (Rr) ‹ desl.dir(010110000) = (01011000)
5. i ‹ 1; i < 4, ir para 2.
2. m1 = 0, c = 0, continuar em 4.
4. (Rr) ‹ desl.dir(0010110000) = (00101100)
5. i ‹ 2; i < 4, ir para 2.
2. m2 = 1, continuar em 3.
3. R ‹ 0010 + 1011 = 1101; c = 0
4. (Rr) ‹ desl.dir(011011100) = (01101110)
5. i ‹ 3; i < 4, ir para 2.
2. m3 = 1, continuar em 3.
3. R ‹ 0110 + 1011 = 0001; c = 1
4. (Rr) ‹ desl.dir(100011110) = (10001111)
5. i ‹ 4; fim. Resultado = 10001111.
2. Multiplicar 11010 por 1111.
1. i ‹ 0, R ‹ 0, r ‹ 0, M ‹ 11010, m ‹ 01111.
2. m0 = 1, continuar em 3.
3. R ‹ 0 + 11010 = 11010; c = 0
4. (Rr) ‹ desl.dir(01101000000) = (0110100000)
5. i ‹ 1; i < 5, ir para 2.
2. m1 = 1, continuar em 3.
3. R ‹ 01101 + 11010 = 00111; c = 1
4. (Rr) ‹ desl.dir(10011100000) = (1001110000)
5. i ‹ 2; i < 5, ir para 2.
2. m2 = 1, continuar em 3.
3. R ‹ 10011 + 11010 = 01101; c = 1
6-20
4. (Rr) ‹ desl.dir(10110110000) = (1011011000)
5. i ‹ 3; i < 5, ir para 2.
2. m3 = 1, continuar em 3.
3. R ‹ 10110 + 11010 = 10000; c = 1
4. (Rr) ‹ desl.dir(11000011000) = (1100001100)
5. i ‹ 4; i < 5, ir para 2.
2. m4 = 0, c = 0, continuar em 4.
4. (Rr) ‹ desl.dir(01100001100) = (0110000110)
5. i ‹ 5; fim. Resultado = 110000110.
3. Sugestões de valores para outros exercícios:
a) Multiplicar 11001 por 10111.
b) Multiplicar 1101 por 101.
c) Multiplicar 110000 por 110100.
d) Multiplicar 101 por 1000.
e) Multiplicar 110 por 111.
Respostas:
a) Produto = 1000111111
b) Produto = 1000001
c) Produto = 100111000000
d) Produto = 101000
e) Produto = 101010
4. Dividir 10010100 por 1011:
Tem-se que D = 10010100 e v = 1011. Então inicia-se a aplicação do algoritmo (seção 4.3):
1. r ‹ 10010, i ‹ 4
2. r ‡ v (10010 ‡ 1011). Então r ‹ 10010 – 1011 = 0111 e q ‹ 1
3. i ‹ 3
4. r ‹ 01111, q ‹ 1x
2. r ‡ v (01111 ‡ 1011). Então r ‹ 01111 – 1011 = 0100 e q ‹ 11
3. i ‹ 2
4. r ‹ 01000, q ‹ 11x
2. r < v (01000 < 1011). Então q ‹ 110
3. i ‹ 1
4. r ‹ 10000, q ‹ 110x
2. r ‡ v (10000 ‡ 1011). Então r ‹ 10000 – 1011 = 0101 e q ‹ 1101
3. i ‹ 0, encerrar. Quociente = 1101 e resto = 0101
5. Dividir 1100101001 por 1111:
Tem-se que D = 1100101001 e v = 11111. Então:
1. r ‹ 110010, i ‹ 5
2. r ‡ v (110010 ‡ 11111). Então r ‹ 110010 – 11111 = 10011 e q ‹ 1
3. i ‹ 4
4. r ‹ 100111, q ‹ 1x
2. r ‡ v (100111 ‡ 11111). Então r ‹ 100111 – 11111 = 1000 e q ‹ 11
3. i ‹ 3
4. r ‹ 010000, q ‹ 11x
6-21
2. r < v (010000 < 11111). Então q ‹ 110
3. i ‹ 2
4. r ‹ 100000, q ‹ 110x
2. r ‡ v (100000 ‡ 11111). Então r ‹ 100000 – 11111 = 00001 e q ‹ 1101
3. i ‹ 1
4. r ‹ 000011, q ‹ 1101x
2. r < v (000011 < 11111). Então q ‹ 11010
3. i ‹ 0, encerrar. Quociente = 11010 e resto = 11
6. Sugestões de valores para outros exercícios:
a) Dividir 1000111111 por 11001.
b) Dividir 1000101 por 1101.
c) Dividir 100111011000 por 110000.
d) Dividir 101010 por 101.
e) Dividir 101010 por 110.
Respostas:
a) Quociente = 10111 e resto = 0
b) Quociente = 101 e resto = 100
Obs.: Se você obteve resposta incorreta para este exercício, verifique quantos dígitos
usou para representar D (D deve ter 2n bits)
c) Quociente = 110100 e resto = 11000
d) A aplicação do algoritmo da seção 6.3 não é possível, uma vez que obtém-se resto
igual ao divisor no passo 2. Usando a divisão “convencional” obtém-se: quociente =
1000 e resto = 10 (ocorre estouro de representação no quociente).
e) Quociente = 111 e resto = 0