Признать силу двух целых чисел

Question

У меня есть число, и оно равно 2. (пример: 2^k) Я хочу получить значение k без использования цикла, деления или какой-либо функции? бит функционирование, плюс, вычесть, состояние можно использовать. Некоторая помощь, пожалуйста, если у вас есть алгоритм или код.

Answer 1

У меня есть число, и это сила 2. (например: 2^к) я хочу, чтобы получить значение к без использования цикла

Некоторых процессоров MIPS имеет CLZ инструкции для подсчета число начальных нулей. Если вы инвертируете результат из этой команды, вы получаете индекс первого бита набора.

Если у вас нет инструкции CLZ, вы можете достичь той же цели следующим образом. Там может быть более компактными реализации, но это, по крайней мере, филиал менее реализации для нахождения log2 целого числа (это вариант this):

# The number to find log2 of 
li $t0,512 

li $t1,0  
li $t2,0xFFFF0000 
and $t3,$t2,$t0 
sltu $t4,$zero,$t3 # if (($t0 & 0xFFFF0000) == 0) { 
xori $t4,$t4,1 
sll $t4,$t4,4 
addu $t1,$t1,$t4  # $t1 += 16 
sllv $t0,$t0,$t4  # $t0 <<= 16 } 
sll $t2,$t2,8 # $t2 = 0xFF000000 
and $t3,$t2,$t0 
sltu $t4,$zero,$t3 # if (($t0 & 0xFF000000) == 0) { 
xori $t4,$t4,1 
sll $t4,$t4,3 
addu $t1,$t1,$t4 
sllv $t0,$t0,$t4 
sll $t2,$t2,4 
and $t3,$t2,$t0 
sltu $t4,$zero,$t3 # if (($t0 & 0xF0000000) == 0) { 
xori $t4,$t4,1 
sll $t4,$t4,2 
addu $t1,$t1,$t4 
sllv $t0,$t0,$t4 
sll $t2,$t2,2 
and $t3,$t2,$t0 
sltu $t4,$zero,$t3 # if (($t0 & 0xC0000000) == 0) { 
xori $t4,$t4,1 
sll $t4,$t4,1 
addu $t1,$t1,$t4 
sllv $t0,$t0,$t4 
sll $t2,$t2,1 
and $t3,$t2,$t0 
sltu $t4,$zero,$t3 # if (($t0 & 0x80000000) == 0) { 
xori $t4,$t4,1 
addu $t1,$t1,$t4 
xori $t0,$t1,31  # $t1 holds the number of leading zeroes; invert to get the highest set bit 
# The output is in $t0 

Answer 2

Почему вы не можете использовать петлю, если я можно спросить? Это классный проект, в котором вам говорят сделать это определенным образом? Если нет, то цикл будет намного проще кодировать и проще понять:

.text 
# The number to find log2 of 
li $t0,512 

add $t1, $zero, $zero # init counter with 2^0 
addi $t2, $zero, 1 # init mask 

loop: 
and $t3, $t0, $t2 # mask all but current bit 
bne $t3, $zero, done 

# Current bit of $t1 is zero. Look at the next one to the left. 
sll $t2, $t2, 1 # shift mask 
addi $t1, $t1, 1 # bump counter 
j loop 

done: 
# $t1 contains power of 2 (original number = 2^$t1) 

Предостережение: этот код не проверяет, действительно ли это сила 2, и это бесконечный цикл для 0! Эти проверки оставлены в качестве упражнения для ученика. :)