Dados x=0101 e y=1010, na notação em complemento de dois (isto é, x=5 e y=-6 ), calcule o resultado de p=x \times y usando o algoritmo de Booth.

Passo 1

O enunciado dá:
x = 0101 e y = 1010 na notação em complemento de dois (isto é, x=5 e y=-6). Pede-se calcular p = x \times y usando o algoritmo de Booth.
Informações relevantes que temos de início:
  • Representações em 4 bits: x = 0101, y = 1010.
  • Vamos trabalhar com multiplicador Q = y e multiplicando M = x.
  • O resultado final deve caber em 8 bits (concatenação de dois registradores de 4 bits: A e Q).

Passo 2

O algoritmo de Booth (modo clássico para multiplicação com sinais) usa estes registros:
  • A: acumulador, inicializado em 0000 (4 bits aqui).
  • Q: registrador do multiplicador (inicialmente y).
  • Q_{-1}: bit extra inicializado em 0.
  • M: multiplicando (aqui x).
    Regras por iteração (olhando o par (Q_0,Q_{-1}), onde Q_0 é o bit menos significativo de Q):
  • (0,0) ou (1,1): não faz operação em A.
  • (0,1): faz A \leftarrow A + M.
  • (1,0): faz A \leftarrow A - M (equivalente a A \leftarrow A + (-M)).
    Depois da operação (ou se não houver operação) faz-se uma rotação à direita aritmética no bloco [A,Q,Q_{-1}] (ou seja, deslocamento à direita com réplica do bit de sinal de A). Repetir por n iterações (aqui n=4).

Passo 3

Configuração inicial:
M = 0101,\quad Q = 1010,\quad A = 0000,\quad Q_{-1} = 0.
Precisamos também de -M em complemento de dois (4 bits). Para obter -M:
inverte-se M e soma-se 1:
\text{inverso de }0101 = 1010,\qquad 1010 + 1 = 1011.
Logo -M = 1011. Vou executar 4 iterações; em cada iteração mostro (Q_0,Q_{-1}), a operação feita, o novo A antes do shift, e o resultado do shift (novo A,Q,Q_{-1}).

Passo 4

Iteração 1 (antes): A=0000,\;Q=1010,\;Q_{-1}=0.
Pegamos Q_0=0 e Q_{-1}=0 → par (0,0)não faz operação em A. Portanto A permanece 0000.
Agora faz-se o deslocamento aritmético à direita em [A,Q,Q_{-1}]:
concatenação antes do shift: 0000\;1010\;0. Deslocando à direita (com sinal de A = 0):
  • novo A = 0000,
  • novo Q = 0101,
  • novo Q_{-1} = 0.
    Resumo Iteração 1 (depois do shift): A=0000,\;Q=0101,\;Q_{-1}=0.

Passo 5

Iteração 2 (antes): A=0000,\;Q=0101,\;Q_{-1}=0.
Aqui Q_0=1 e Q_{-1}=0 → par (1,0)subtrair M (ou somar -M). Calculamos:
A \leftarrow A + (-M) = 0000 + 1011 = 1011.
Agora faz-se o deslocamento aritmético à direita de 1011\;0101\;0:
  • novo A = 1101,
  • novo Q = 1010,
  • novo Q_{-1} = 1.
    Resumo Iteração 2 (depois do shift): A=1101,\;Q=1010,\;Q_{-1}=1.

Passo 6

Iteração 3 (antes): A=1101,\;Q=1010,\;Q_{-1}=1.
Agora Q_0=0 e Q_{-1}=1 → par (0,1)somar M. Calculamos:
A \leftarrow A + M = 1101 + 0101.
Fazendo a soma bit a bit (sem expandir para mais bits):
  • 1101 + 0101 = 0010 (em 4 bits; carry final é descartado). Observação decimal: -3 + 5 = 2, que bate com 0010.
    Agora deslocamento aritmético à direita de 0010\;1010\;1:
  • novo A = 0001,
  • novo Q = 0101,
  • novo Q_{-1} = 0.
    Resumo Iteração 3 (depois do shift): A=0001,\;Q=0101,\;Q_{-1}=0.

Passo 7

Iteração 4 (antes): A=0001,\;Q=0101,\;Q_{-1}=0.
Aqui Q_0=1 e Q_{-1}=0 → par (1,0)subtrair M novamente:
A \leftarrow A + (-M) = 0001 + 1011 = 1100.
(Confirmação decimal: 1 - 5 = -4 1100.)
Faz-se o deslocamento aritmético à direita final de 1100\;0101\;0:
  • novo A = 1110,
  • novo Q = 0010,
  • novo Q_{-1} = 1.
    Resumo Iteração 4 (depois do shift): A=1110,\;Q=0010,\;Q_{-1}=1.

Passo 8

O algoritmo terminou após n=4 iterações. O produto final p está na concatenação A seguido de Q (8 bits):
p = A\;Q = 1110\;0010.
Para verificar o valor decimal: em complemento de dois com 8 bits 11100010 representa um número negativo. Calculando seu valor:
inverter 11100010 \rightarrow 00011101, somar 1 \rightarrow 00011110 que é 30 em decimal, logo o número é -30. Isso confere com 5 \times (-6) = -30.

Resposta

\,p = 11100010_{(2)} = -30

Exercícios relacionados