Какова логика MIPS этого отношения $ s1 = floor (log2 ($ t0))?

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

Цикл подсчитывает количество последовательных сдвигов вправо (то есть деления на 2), которые могут быть выполнены на $t0 без результата, равного нулю.

Это также может быть выражено как нахождение (ноль-на основе) положение самого левого 1 -бит в $t0. И поскольку нас заботит только крайний левый 1, мы можем, в свою очередь, выразить это как нахождение наибольшего целого числа z , такого, что 2 ^z <= <strong>$ t0 .

Мы можем воспользоваться преимуществом взаимосвязи между логарифмами и возведением в степень, а именно:

log _b (m) = n если b ⁿ = m

Итак $ t0 = 2 ⁿ где n = log ₂ ($ t0) , что также означает, что $ t0 = 2 ^{log ₂ ($ t0)}

Таким образом, нам интересно найти наибольшее целое число z , такое, что 2 ^z <= 2 <sup>log ₂ ($ t0)

Поскольку 2 ^x является монотонно возрастающей функцией, из этого следует, что 2 ^x <= 2 <sup>y для x <= y </strong>. Таким образом, мы можем упростить то, что мы ищем, до наибольшего целого числа z , такого что z <= log <sub>2 ($ t0) , которое является определением пол (журнал ₂ ($ t0)) .