我刚刚参加了期末考试,有一道题目在限制条件下似乎不可能。我很高兴被证明是错误的,但据我核实,至少我所有的同学都同意我的结论。这是我提供的问题和答案:
提供一个C程序片段如下:
c = a + b + 6;
while (c > 5) {
c = c - a;
b = b + 1;
}
使用最多 7 条指令在 MIPS 汇编中编写等价物,仅使用以下指令集:
add, addi, sub, subi, slt, slti, bne
a、b 和 c 分别通过寄存器 $t0、$t1 和 $s0 访问。您可以根据需要使用其他寄存器,但您不能假定任何初始值。
这是我用尽可能少的几行给出的答案:
add $s0, $t0, $t1
addi $s0, $s0, 6
loop: slti $t2, $s0, 6
bne $t2, $0, skip
sub $s0, $s0, $t0
addi $t1, $t1, 1
skip: subi $t2, $t2, 1
bne $t2, $0, loop
在 3 小时的考试中,我考虑了整整 30 分钟,我想出了两种可能是教授在这道题上弄错的可能性。对我来说更有可能的是他希望我们编写一个 do-while
循环。另一个可能性较小的是我们被允许在其他指令之外使用 beq
。以下是我对这些问题的回答:
同时做:
add $s0, $t0, $t1
addi $s0, $s0, 6
loop: sub $s0, $s0, $t0
addi $t1, $t1, 1
slti $t2, $s0, 6
subi $t2, $t2, 1
bne $t2, $0, loop
beq
允许:
add $s0, $t0, $t1
addi $s0, $s0, 6
loop: slti $t2, $s0, 6
bne $t2, $0, skip
sub $s0, $s0, $t0
addi $t1, $t1, 1
skip: beq $t2, $0, loop
我挑战任何人找到一个更短的答案或最终证明一个更短的答案是不可能的,这一直困扰着我。
更新
我和我的教授一起复习了我的期末成绩,虽然他拒绝提供答案,但他声称全类有一半的人都答对了。我发现我的教授未能提供现有答案的证据,同时以此作为从我的考试中扣分的基础,这是不公平的,但我无能为力证明我的观点,并且考虑到这一点是不明智的期末平均分较低的曲线,我为全类赢得了 4.0 分。
虽然我仍然持怀疑态度,因为我发现他对我的一个 Verilog 代码片段进行了错误评分,在与他一起复习我的期末考试后我获得了满分,所以我找到了一个在 MIPS 汇编问题上获得满分的人。他告诉我他的策略,但不记得他的确切答案,所以我根据@Smac89 的回答帮他重新创建了它:
addi $t2, $t0, 6 # d = a + 6
add $s0, $t2, $t1 # c = d + b
bne $t2, $t0, comp # (d != a) ? comp
loop: sub $s0, $s0, $t0 # c = c - a;
addi $t1, $t1, 1 # b = b + 1;
comp: slti $t2, $s0, 6 # d = (c < 6)
subi $t2, $t2, 1 # invert the flag
bne $t2, $0, loop # !(c < 6) ? loop
所以,这也行不通。他采用的具体策略是,他在循环的顶部有一个有保证的分支,他分两行检查底部的条件。但是我想不出一种方法来使用 slt
或 slti
创建一个有效的标志来检查 bne
。无论他在 7 行中尝试什么,教授都可能给错误评分。
总而言之,我仍然没有答案。
最佳答案
建立在 Smac89 的答案之上,这保证了除非循环完成,否则 C 不为 0,因此 C 的值可用于分支。
add $s0, $t0, $t1 # c = a + b
loop: slti $t2, $s0, 0 # while (is c less than 0?
bne $t2, $zero, exit # (c > 5)
sub $s0, $s0, $t0 # c = c - a;
addi $t1, $t1, 1 # b = b + 1;
bne $t2, $s0, loop # Loop again unless s0 is 0 -- then we're done
exit: addi $s0, $s0, 6 # add the missing 6
关于用 7 条指令将 C 语言编译成 MIPS 汇编语言?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37018833/