c - 这个关系 $s1 = Floor( log2 ($t0) ) 的 mips 逻辑是什么？

Question

这是给出的 C 片段代码。

     addi $s1, $zero, 0

 loop: srl $t0, $t0, 1

     beq $t0, $zero, exit
     addi $s1, $s1, 1
     j loop 
exit

有人问我 $s1 和 $t0 之间是什么关系。从C代码中我可以看出$t0 每次循环右移 1 位 ($t0 = $t0/2)，直到变为 0 并且$s1 就是 $s1 = $s1 + 1，每个循环加 1该关系的答案是 $s1 = Floor( log2 ($t0) )，但我不明白这种关系背后的逻辑。谁可以给我解释一下这个？谢谢

Answer 1

循环计算可以在 $t0 上执行的连续右移(即除以 2)的次数，且结果不为零。

这也可以表示为查找 $t0 中最左边 1 位的(从零开始的)位置。由于我们只关心最左边的 1，我们可以依次将其表示为找到最大整数 z，使得 2^z <= $t0。

我们可以利用对数和指数之间的关系，那就是

log_b(m) = n  如果  bⁿ = m

所以$t0 = 2ⁿ，其中n = log₂($t0)，这也意味着$t0 = 2^log₂($t0)

因此，我们有兴趣找到最大整数 z，使得 2^z <= 2^{log₂( $t0)}

由于 2^x 是单调递增函数，因此 2^x <= 2^y 表示 x <= y。因此，我们可以将我们正在寻找的最大整数 z 简化为 z <= log₂($t0)，即floor(log₂($t0)) 的定义。