MIPS（汇编） - 二进制搜索问题 - 中间数组元素的地址未对齐？

Question

        .text
        j main
        
binary_search:       
        slt $t0, $a2, $a1 # if last < first, $t0 = 1
        beq $t0, $zero, check_mid # if first > last, proceed to return -1   
    
        addi $v0, $zero, -1
        jr $ra # exit with returned argument
        
check_mid:
        # saving address to stack
        addi $sp, $sp, -4
        sw $ra, 4($sp)
             
        sub $t1, $a2, $a1 # last - first
        srl $t1, $t1, 1 # (last - first) /2
     
        add $t2, $a1, $t1 # $t2 is referrencing the mid index of the array
        lw  $t3, 0($t2) # $t3 is the mid element of the array
        
        bne $t3, $a0, check_higher
    
        add $v0, $t2, $zero # $v0 is the index of the wanted element
        
        lw $ra, 4($sp)
        addi $sp, $sp, 4
        
        jr $ra # exit with returned argument
    
check_higher: 
        slt $t0, $t3, $a0 # if arr[mid] < x, $t0 is 1
        bne $t0, $zero, check_lower              
    
        addi $t1, $t1, -4 # mid = mid - 4
        jal binary_search # recursion call                
     
check_lower:
        addi $t1, $t1, 4 # mid = mid + 4
         jal binary_search # recursion call            
                      
main:
        addi $a0, $zero, 64
        addi $a1, $zero, 0
        addi $a2, $zero, 28
        jal binary_search

所以这是我到目前为止的代码。据我所知，我对代码几乎完成了，除非我不太照顾堆栈中保存/加载返回地址，但这不是我现在的主要关注点。

我想弄清楚的是，如何达到数组的中间偏移/元素？因为执行此代码会给我带来错误：“行39：运行时异常在0x00400028：未在Word Boundare 0x0000000e上对齐的地址”（第39行是此行：lw $ t3，0（$ t2）＃$ T3是数组的中元）

Answer 1

看来您正在使用字节偏移而不是单词索引。这很好且良好（而不是每次使用地址时重做左移动），但这意味着正确的偏移不会截断为单词偏移，而是可以转移到该字节的字节中的一部分地址，低2个字节。与C不同，如果您做了MID =（HI-LO）＆gt; 1;，它只会将值的底部移出。

srl $ t1，$ t1，1因此可以产生一个奇怪的半词地址，而不是将其截断为对齐的单词地址。

您可以使用和使用-4，即0xfffffffc在移动后清除那些地址位，但是MIPS无法在一个指令中这样做，因为<代码> andi 零扩展其即时。如果您的数组真的很小于64KIB，并且在非常低的地址接近零（因此0x0000000e您尝试deref也不是将小偏移添加到一个的单独错误null指针），您可以使用 0x0000fffc 来截断地址。或者，如果您要使用偏移而不是实际指针，请在将其添加到实际地址之前，然后将其添加到实际地址。

当然，您可以在循环之前一次li $ t9，-4一次使用，但是您使用的是递归而不是更有效的循环。因此，我想您无论如何都不在乎效率，并且可以在要和之前就可以做一个额外的li。 （addiu可以在一个指令中实现-4，不同于ori。）

---

或另一种方法是正确地移动您想要的位将所有路程都从寄存器中删除，然后左右移动，将数据带回您想要的位置。 mid =（（Hi-lo）＆gt;＆gt; 3）＆lt;＆lt;＆lt; 1;

---

也有其他错误，例如在JAL BINARY_SERACH in check_lower中掉落函数的底部：返回。您要么需要重新加载$ ra并在这些路径中返回，要么在重新加载后将尾巴呼叫到j b b $ ra ，不是jal/reload $ ra/jr $ ra。

jal在check_higher中相同：;您不想陷入check_lower，最终会检查两侧的总运行时，而不是O（log n）。

但是，这些都是您应该通过调试器单步步进行调试的所有事情，并与有趣的右移问题分开，在使用单词地址或字节偏移的ASM中进行二进制搜索时，可以创建一个奇怪的halfword地址。