1

我有一个数字，它是 2 的幂。（例如：2^k）我想在不使用循环、除法或任何类型的函数的情况下获得 k 的值？位操作，加，减，条件都可以使用。如果您有任何算法或代码，请提供一些帮助。

4

2 回答 2

2

我有一个数字，它是 2 的幂。（例如：2^k）我想在不使用循环的情况下获得 k 的值

一些 MIPS CPU 具有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
于 2013-10-11T11:34:45.567 回答
1

如果我可以问，为什么不允许使用循环？这是一个课堂项目，你被告知以特定的方式去做吗？如果没有，循环会更容易编码和更容易理解：

.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 的无限循环！这些验证留给学生作为练习。:)

于 2013-10-16T18:56:42.857 回答