assembly - 整数の 2 乗を認識する

Question

数値があり、それは 2 のべき乗です (例: 2^k) ループ、除算、またはその他の関数を使用せずに k の値を取得したいですか? ビット演算、プラス、減算、条件が使用できます。アルゴリズムやコードがあれば、助けてください。

Answer 1

私は数を持っていて、それは 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

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 の無限ループです! これらの検証は、学生の演習として残されています。:)