Recogniz冪的兩個整數

Question

我有一個數字，它是2的冪。（例如：2^k） 我想獲得k的值，而不使用循環，除法或任何類型的函數？ 位操作，加，減，條件都可以使用。 有些幫助，如果你有任何算法或代碼。

Answer 1

我有一個數字，它是2的冪（例如：2^k）的我想獲得k的值，而無需使用環

有些MIPS CPU具有用於計數一個CLZ指令前導零的數量。如果反轉該指令的結果，則會得到第一個設置位的索引。

如果您沒有CLZ指令，您可以通過以下方式實現相同的目的。有可能是更緊湊的實現，但是這至少找到一個整數的log 2分支少的實現（它是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！這些驗證留給學生練習。 :)