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) )，但我不明白这种关系背后的逻辑。谁可以给我解释一下这个？谢谢

标签： cmips

Answer 1

$t0循环计算可以在结果不为零的情况下执行的连续右移次数（即除以 2） 。

这也可以表示为在 中找到最左边1位的（从零开始的）位置$t0。由于我们只关心最左边的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是一个单调递增的函数，因此对于x <= y来说2 ^x <= 2 ^y。所以我们可以将我们正在寻找的最大整数z简化为z <= log ₂ ($t0)，这是floor(log ₂ ($t0))的定义。