( 1,0 pontos) O seguinte fragmento de código processa dois arrays e produz um valor importante no registrador \ \mathrm{v} 0 . Considere que cda array consista em 2500 words indexados de 0 a 2499 , que os endereços base dos arrays sejam armazenados emç$\mathrm{a} 0 e$ \mathrm{a} 1 , respectivamente, e que seus tamanhos (2500) sejam armazenados em \a2 e $a3, respectivamente. Acrescente comentários ao código e descreva em uma sentença o que o código faz. Especificamente, o que será retornado em $v0?
sll $a2, $a2, 2
sll $a3, $a3, 2
add $v0, $zero, $zero
add $t0, $zero, $zero
outer: add $t4, $a0, $t0
Iw $t4, 0($t4)
add $t1, $zero, $zero
inner: add $t3, $a1, $t1
Iw $t3, 0($t3)
bne $t3, $t4, skip
addi $v0, $v0, 1
skip: addi $t1, $t1, 4
bne $t1, $a3, inner
addi $t0, $t0, 4
bne $t0, $a2, outer

Passo 1

O enunciado dá um fragmento de código em estilo MIPS que processa dois arrays. As informações fornecidas são:
  • Cada array tem exatamente 2500 words, indexadas de 0 a 2499.
  • O endereço base do primeiro array (chamei de A) está em \$a0.
  • O endereço base do segundo array (chamei de B) está em \$a1.
  • O tamanho 2500 está em \$a2 (para A) e em \$a3 (para B).
  • O código atual usa registradores temporários \$t0,\$t1,\$t3,\$t4 e o registrador de contagem \$v0.
    O pedido: acrescente comentários ao código e descreva em uma sentença o que o código faz — especificamente, o que será retornado em \$v0.

Passo 2

Aqui está o código com comentários linha a linha (cada registrador e número aparece entre ... conforme solicitado):
sll \$a2, \$a2, 2 # multiplica o tamanho de A por 4: converte contador de words para bytes
sll \$a3, \$a3, 2 # multiplica o tamanho de B por 4: converte contador de words para bytes
add \$v0, \$zero, \$zero # zera o contador de correspondências em $v0
add \$t0, \$zero, \$zero # zera o offset byte para percorrer A
outer: add \$t4, \$a0, \$t0 # calcula endereço efetivo de A[i]: base A + offset t0
lw \$t4, 0(\$t4) # carrega A[i] em $t4
add \$t1, \$zero, \$zero # zera o offset byte para percorrer B
inner: add \$t3, \$a1, \$t1 # calcula endereço efetivo de B[j]: base B + offset t1
lw \$t3, 0(\$t3) # carrega B[j] em $t3
bne \$t3, \$t4, skip # se B[j] diferente de A[i], pula incremento
addi \$v0, \$v0, 1 # se igual, incrementa contador de correspondências
skip: addi \$t1, \$t1, 4 # t1 += 4 (próxima word de B)
bne \$t1, \$a3, inner # enquanto t1 != tamanho_em_bytes_de_B, repete inner
addi \$t0, \$t0, 4 # t0 += 4 (próxima word de A)
bne \$t0, \$a2, outer # enquanto t0 != tamanho_em_bytes_de_A, repete outer

Passo 3

Explanação didática das duas primeiras instruções ( sll) e por que são necessárias:
  • Em MIPS a memória é endereçada por bytes. Cada word tem 4 bytes. O enunciado guardou em \$a2 e \$a3 o número de words ( 2500), não o número de bytes.
  • A instrução sll \(\$a2\), \(\$a2\), 2 faz um shift lógico à esquerda por 2 bits: isso equivale a multiplicar por 2^2=4. Portanto: 2500 \cdot 4 = 10000,então depois dessa instrução \$a2=10000 (bytes). O mesmo vale para \$a3.
  • Conclusão prática: as comparações posteriores usam offsets em bytes (0, 4, 8, …), e as instruções bne com \$t0 e \$a2 comparam offsets em bytes.

Passo 4

O que fazem as inicializações e qual o papel de \$t0 e \$t1:
  • add \(\$v0\), \(\$zero\), \(\$zero\) inicializa \$v0 com 0. Vamos usar \$v0 para contar quantas vezes encontramos elementos iguais entre A e B.
  • add \(\$t0\), \(\$zero\), \(\$zero\) inicializa \$t0 com 0. \$t0 é usado como offset em bytes para percorrer A: na iteração i tem valor \$t0 = 4\cdot i.
  • Dentro do laço externo, add \(\$t1\), \(\$zero\), \(\$zero\) inicializa \$t1 com 0 para cada novo i. \$t1 é o offset em bytes para percorrer B: na iteração j tem valor \$t1 = 4\cdot j.

Passo 5

Como o carregamento e comparação funcionam (a instrução lw e o bne):
  • add \(\$t4\), \(\$a0\), \(\$t0\) calcula o endereço de A[i] como base A + offset t0. Em seguida lw \(\$t4\), \(0(\$t4)\) carrega a word de memória nesse endereço para \$t4. Assim \$t4 passa a conter A[i].
  • De modo análogo, add \(\$t3\), \(\$a1\), \(\$t1\) e lw \(\$t3\), \(0(\$t3)\) carregam B[j] em \$t3.
  • bne \(\$t3\), \(\$t4\), skip testa se B[j] \neq A[i]. Se forem diferentes, pula o incremento. Se forem iguais, a instrução seguinte addi \(\$v0\), \(\$v0\), 1 aumenta o contador.

Passo 6

Estrutura de laços (loops) e contagem total de comparações:
  • O laço externo percorre i de 0 até 2499 (em offsets de bytes 0,4,8,\dots,4\cdot2499). O laço interno percorre j de 0 até 2499.
  • Para cada par (i,j) o código compara A[i] com B[j] e, se iguais, incrementa \$v0.
  • Número total de comparações realizadas é 2500 \times 2500 = 6\,250\,000. O contador \$v0 conta quantas dessas comparações resultaram em igualdade.

Passo 7

Observação importante sobre duplicatas e o que exatamente é contado:
  • O código não faz distinção de posições já contadas nem elimina duplicatas de valores; ele conta todas as ocorrências par-a-par.
  • Ou seja, se um valor x aparece m vezes em A e n vezes em B, então ele contribui com m\cdot n para o total \$v0.
  • Exemplo pequeno (para entender): se A=[1,2,1] e B=[1,1],
    • para A[0]=1 2 correspondências (com B[0] e B[1]);
    • para A[1]=2 0;
    • para A[2]=1 há mais 2;
    • total \$v0 = 2+0+2 = 4.

Passo 8

Resumo prático de como interpretar o resultado em uma prova:
  • Ao ver esse código, você deve reconhecer imediatamente: (1) conversão de contadores de words para bytes via deslocamento à esquerda por 2; (2) uso de offsets em bytes, \$t0 e \$t1, para indexação; (3) dois laços aninhados que comparam cada par de elementos; (4) incremento de \$v0 quando um par é igual.
  • Portanto, sem ter de executar todas as 6,25 milhões de comparações na prova, descreva logicamente que \$v0 terminará contendo o número total de pares (i,j) com 0\le i,j\le 2499 tais que A[i]=B[j].

Passo 9

Uma sentença que descreve o que o código faz (pedida no enunciado):
  • O código conta todas as ocorrências onde um elemento de A é igual a um elemento de B, somando 1 para cada par (i,j) com A[i]=B[j], e armazena essa contagem em \$v0.

Resposta

\$v0 conterá o número total de pares (i,j) com 0\le i,j\le 2499 tais que A[i]=B[j].

Exercícios relacionados