arrays - 如何在MIPS中找到数组的最小值

Question

这是我的代码，我无法获得正确的输出。我哪里错了？我最初将 min 设置为零，然后检查数组是否小于或等于该值，如果是，则跳转到标签并使 min 的值成为数组的值，然后跳回迭代数组。

xyz:    .word   -8, 16, -32, 64, -128, 256 

# int main(void)
#
# local variable    register
#   int *p      $s0
#   int *end    $s1
#   int min     $s2  
#   int total   $s3
#   
    .text
    .globl  main
main:
    la  $s0, xyz                # p = foo
    addi    $s1, $s0, 24        # end = p + 6
    add $s3, $zero, $zero       # total = 0 
    add     $s2, $zero, $zero   # min = 0
L1:
    beq $s0, $s1, L2    # if (p == end) goto L2
    lw  $t0, ($s0)      # $t0 = *p
    lw  $t1, ($s2)      # $t1 = min
    slt $t2, $t1, $t0       # check if min is less than p
    add $s3, $s3, $t0       # total += $t0
    bne     $t2, $zero, L3      # if min is less than p, go to L3 
    addi    $s0, $s0, 4     # p++
    j   L1
L2:     
    add $v0, $zero, $zero   # return value from main = 0
    jr  $ra

L3:
    move    $s2, $t0
    j   L1

Answer 1

好的，我发现了几个错误。我创建了三个版本，并添加了输出系统调用，以便您可以看到结果[请原谅无偿的风格清理]:

<小时/>

这是您的原始代码，其中包含错误注释:

    .data
xyz:        .word       -8,16,-32,64,-128,256

# int main(void)
#
# local variable    register
#   int *p      $s0
#   int *end    $s1
#   int min     $s2
#   int total   $s3
#
    .text
    .globl  main

main:
    la      $s0,xyz                 # p = foo
    addi    $s1,$s0,24              # end = p + 6
    add     $s3,$zero,$zero         # total = 0

    # NOTE/BUG: to find minimum, you want to init this to the first array
    # element
    # also, initializing with a minimum value (e.g. 0), or more correctly, the
    # largest possible negative number (e.g. 0x80000000) implies a search for
    # maximum
    add     $s2,$zero,$zero         # min = 0

L1:
    beq     $s0,$s1,L2              # if (p == end) goto L2
    lw      $t0,($s0)               # $t0 = *p

    # NOTE/BUG: s2 is a register variable that contains "min" (e.g. int min)
    # and is _not_ a pointer to a "min" variable in memory (e.g. int *min)
    lw      $t1,($s2)               # $t1 = min

    # NOTE/BUG: the the check should be reversed:
    slt     $t2,$t1,$t0             # check if min is less than p
    add     $s3,$s3,$t0             # total += $t0

    bne     $t2,$zero,L3            # if min is less than p, go to L3

    # NOTE/BUG: this pointer increment is out of place (i.e. it does not
    # get incremented if there is a jump to L3)
    # this won't affect the min value, but it will double count the value in
    # the total
    addi    $s0,$s0,4               # p++
    j       L1

L2:
    add     $v0,$zero,$zero         # return value from main = 0
    jr      $ra

L3:
    move    $s2,$t0
    j       L1

<小时/>

这是一个固定版本:

    .data
xyz:        .word       -8,16,-32,64,-128,256
msg_min:    .asciiz     "min: "
msg_tot:    .asciiz     " total: "
msg_nl:     .asciiz     "\n"

# int main(void)
#
# local variable    register
#   int *p      $s0
#   int *end    $s1
#   int min     $s2
#   int total   $s3
#
    .text
    .globl  main

main:
    la      $s0,xyz                 # p = foo
    addi    $s1,$s0,24              # end = p + 6
    add     $s3,$zero,$zero         # total = 0

    lw      $s2,0($s0)              # min = xyz[0]

L1:
    beq     $s0,$s1,L2              # if (p == end) goto L2

    lw      $t0,0($s0)              # $t0 = *p
    addi    $s0,$s0,4               # p++

    add     $s3,$s3,$t0             # total += $t0

    slt     $t2,$t0,$s2             # *p < min?
    bne     $t2,$zero,L3            # yes, fly

    j       L1

L2:
    li      $v0,4
    la      $a0,msg_min
    syscall

    li      $v0,1
    move    $a0,$s2                 # get min value
    syscall

    li      $v0,4
    la      $a0,msg_tot
    syscall

    li      $v0,1
    move    $a0,$s3                 # get total value
    syscall

    li      $v0,4
    la      $a0,msg_nl
    syscall

    # exit program
    li      $v0,10
    syscall

L3:
    move    $s2,$t0                 # set new/better min value
    j       L1

<小时/>

这是一个稍微更干净的版本，我颠倒了分支的感觉，并且能够稍微收紧循环。另外，我更改了标签以更好地描述角色/功能:

    .data
xyz:        .word       -8,16,-32,64,-128,256
msg_min:    .asciiz     "min: "
msg_tot:    .asciiz     " total: "
msg_nl:     .asciiz     "\n"

# int main(void)
#
# local variable    register
#   int *p      $s0
#   int *end    $s1
#   int min     $s2
#   int total   $s3
#
    .text
    .globl  main

main:
    la      $s0,xyz                 # p = foo
    addi    $s1,$s0,24              # end = p + 6
    add     $s3,$zero,$zero         # total = 0

    lw      $s2,0($s0)              # min = xyz[0]

main_loop:
    beq     $s0,$s1,main_done       # if (p == end) goto L2

    lw      $t0,0($s0)              # $t0 = *p
    addi    $s0,$s0,4               # p++

    add     $s3,$s3,$t0             # total += $t0

    slt     $t2,$s2,$t0             # *p < min?
    bne     $t2,$zero,main_loop     # no, loop

    move    $s2,$t0                 # set new/better min value
    j       main_loop

main_done:
    li      $v0,4
    la      $a0,msg_min
    syscall

    li      $v0,1
    move    $a0,$s2                 # get min value
    syscall

    li      $v0,4
    la      $a0,msg_tot
    syscall

    li      $v0,1
    move    $a0,$s3                 # get total value
    syscall

    li      $v0,4
    la      $a0,msg_nl
    syscall

    # exit program
    li      $v0,10
    syscall

<小时/>

更新:

thanks that helped a lot, but lw $t1,($s2) doesnt work because lw will only work on pointers?

对。请注意您如何使用 s3 来保存 total。这就是代码如何使用 s2 来保存最小值。我这样做[部分]是因为最上面的评论:

#   int min     $s2

要使用lw，最上面的注释应该是:

#   int *min    $s2

要以原始方式使用 s2 ，您需要类似以下内容:

min:    .word    0

并且，您需要(在循环开始之前):

la    $s2,min

而且，您必须对其进行 lw 和 sw 操作，这只会减慢速度。因此，除了已有的内容之外，您还需要添加一个额外的 lw 和一个额外的 sw。

mips 有很多寄存器[它的长处]。因此，它可以加快速度以在其中保留自动的函数作用域变量。

但是，为了完整起见，这里有一个允许您使用 lw 的版本。注意额外的内存访问。这很像用 -O0 编译的 C 代码:

    .data
min:        .word       0
xyz:        .word       -8,16,-32,64,-128,256
msg_min:    .asciiz     "min: "
msg_tot:    .asciiz     " total: "
msg_nl:     .asciiz     "\n"

# int main(void)
#
# local variable    register
#   int *p      $s0
#   int *end    $s1
#   int *min    $s2
#   int total   $s3
#
    .text
    .globl  main

main:
    la      $s0,xyz                 # p = foo
    addi    $s1,$s0,24              # end = p + 6
    add     $s3,$zero,$zero         # total = 0

    la      $s2,min                 # point to min
    lw      $t4,0($s0)              # fetch xyz[0]
    sw      $t4,0($s2)              # store in min

main_loop:
    beq     $s0,$s1,main_done       # if (p == end) goto L2

    lw      $t0,0($s0)              # $t0 = *p
    addi    $s0,$s0,4               # p++

    add     $s3,$s3,$t0             # total += $t0

    lw      $t4,0($s2)              # fetch min
    slt     $t2,$t4,$t0             # *p < min?
    bne     $t2,$zero,main_loop     # no, loop

    sw      $t0,0($s2)              # store new/better min value
    j       main_loop

main_done:
    li      $v0,4
    la      $a0,msg_min
    syscall

    li      $v0,1
    lw      $a0,0($s2)              # get min value
    syscall

    li      $v0,4
    la      $a0,msg_tot
    syscall

    li      $v0,1
    move    $a0,$s3                 # get total value
    syscall

    li      $v0,4
    la      $a0,msg_nl
    syscall

    # exit program
    li      $v0,10
    syscall