我刚刚参加了一场期末考试,其中有一道问题在限制条件下似乎是不可能的。如果能证明我错了我会很高兴,但据我所知,至少我的同学都同意我的结论。以下是题目和我提供的答案:
给出如下C程序片段:
c = a + b + 6;
while (c > 5) {
c = c - a;
b = b + 1;
}
使用最多7条指令,只使用以下指令集,在MIPS汇编中写出等效代码:
add, addi, sub, subi, slt, slti, bne
$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
指令以及其他指令。以下是我的答案:
do-while:
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
allowed:
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行中尝试的任何内容进行了错误评分。总之,我仍然没有答案。