1. (1,0 pontos) Encontre a sequência mais curta de instruções MIPS para determinar o valor absoluto de um inteiro em complemento de dois. Converta esta instrução aceita pelo montador.
abs \(t2,\)t3 # cópia absoluto de \(t3 em\)t2

Passo 1

O enunciado pede para converter a pseudo-instrução
\text{abs }\$t2,\\ \$t3
(nota: cópia do valor absoluto de \$t3 em \$t2) na sequência mais curta de instruções MIPS que o montador aceita.
Informações relevantes dadas pelo enunciado:
  • O valor original (um inteiro em complemento de dois) está em \$t3.
  • O resultado (o valor absoluto) deve ficar em \$t2.
  • Podemos usar registradores temporários adicionais se necessário (por exemplo \$t4).
  • Queremos a sequência de instruções real (sem pseudo-instruções) e a mais curta possível.

Passo 2

Breve explicação sobre complemento de dois e negação (pra segurar a intuição):
  • Em complemento de dois, o bit mais significativo é o bit de sinal: se ele for 0 o número é não negativo, se for 1 o número é negativo.
  • A negação aritmética de um inteiro x em complemento de dois é dada por
-x = \sim x + 1,
onde \sim x é o complemento bit-a-bit (bitwise NOT). Isso é importante porque o valor absoluto de x é x quando x\ge 0 e -x quando x<0.

Passo 3

Ideia da solução (sem ainda colocar instruções): precisamos de uma forma de decidir, sem usar branch (pois branch + instruções costuma ser mais longo), se x\) é negativo; com essa decisão, aplicamos ou não a negação. Uma técnica clássica em MIPS é construir uma máscara de 32 bits \(m\) que vale \[m=\begin{cases}0 & \text{se }x\ge 0,\\\\ -1 & \text{se }x<0,\end{cases}
ou seja, m\] é \(0x00000000 para não-negativos e 0xFFFFFFFF para negativos. Usando essa máscara podemos escrever uma fórmula que dá o absoluto sem branches.

Passo 4

Como obter a máscara m com instruções MIPS: deslocamento aritmético à direita por 31 posições replica o bit de sinal por todos os bits. Em MIPS isso é feito por \text{sra}. Se x está em \$t3, então
m = \text{sra}(\$t3,\,31)
produz m=0 quando x\ge0 e m=-1 quando x<0. Isso porque o deslocamento aritmético preserva o sinal.

Passo 5

Agora a fórmula mágica usando m que produz |x| sem branch é
y = (x \oplus m) - m,
onde \oplus é XOR bit-a-bit. Vamos checar por casos:
  • Se m=0 (isto é, x\ge0): y = (x \oplus 0) - 0 = x.
  • Se m=-1 (isto é, x<0). Note que x\oplus (-1) = \sim x. Então y = \sim x - (-1) = \sim x + 1 = -x,que é exatamente o valor absoluto de x. Portanto a expressão funciona.

Passo 6

Tradução direta para instruções MIPS (usando \$t4 como registrador temporário para m). A sequência mínima e típica é de três instruções:
  • calcular m com deslocamento aritmético;
  • fazer XOR entre x e m;
  • subtrair m do resultado.
Escrevendo as instruções (cada registrador entre ... conforme exigido):
sra \$t4,\\ \$t3,\\\ 31
xor \$t2,\\ \$t3,\\ \$t4
subu \$t2,\\ \$t2,\\ \$t4
Explicação rápida da escolha: usei \text{sra} para obter a máscara de sinal, \text{xor} para obter \sim x quando necessário, e \text{subu} (subtração sem overflow) para calcular (x\oplus m)-m. São três instruções, e qualquer solução sem pseudo-instrução e sem branches em MIPS I exige pelo menos essas operações lógicas/aritméticas, então esta é a sequência mais curta prática e amplamente usada.

Passo 7

Exemplo numérico rápido para fixar (pega a intuição): seja x=-5. Em complemento de dois, -5 tem bit de sinal 1.
  • \text{sra}(\\ -5,31) m=-1.
  • -5 \oplus (-1) = \sim(-5).
  • \sim(-5) - (-1) = \sim(-5)+1 = 5. Pronto: obtivemos |-5|=5.

Resposta

sra \$t4,\\ \$t3,\\\ 31
xor \$t2,\\ \$t3,\\ \$t4
subu \$t2,\\ \$t2,\\ \$t4

Exercícios relacionados