Zählen der 1en auf der linken Seite einer binären Darstellung

Question

Ich versuche, die Anzahl der 1 auf der linken Seite zu bekommen (Bits 16-31) Dieser Code scheint zu funktionieren, aber ich bekomme 1 extra Zählung auf meine 1 von sicher ganze Zahlen. Beispiel: 1536 binär ist 0000 0000 0000 0000 | 0000 0110 0000 0000 und ich bekomme 0 1 auf der linken Seite, die korrekt ist.

Auch: 100000 linke Seite binäre ist 0000 0000 0000 0001 und mein Ergebnis ist 1. das ist auch richtig.

Jedoch: 1000000000 binär ist 0011 1011 1001 1010 | 1100 1010 0000 0000 und ich bekomme 10 1 auf der linken Seite anstelle von 9.

Ich habe andere Zahlen getestet, aber sie haben auch eine extra Zählung.

#Displays number of 1's on left half 
    li $v0, 4 
    la $a0, left 
    syscall 

    li $t2, 0 #i = 0 
    srl $t3, $s0, 16 #shifts users number to the right by 16 bits 

Counter: 
    and $t4, $t3, 1 #Mask off bit 
    beq $t4, 1, Count #if mask = 1 go to count 
    srl $t3, $t3, 1 #if mask != 1 (aka 0) shifts right by 1 

    beq $t3, 0, Exit #once the shifted bits = 0 go to exit 

Count:  
    add $t2, $t2, 1 #increment i++ 
    srl $t3, $t3, 1 #shifts right by 1 
    j Counter  

Exit:  
    li $v0, 1 #Displays number of 1's 
    move $a0, $t2 
    syscall 

Nicht sicher, ob der Code sogar richtig ist, seit neu zu Mips. Könnte möglich sein, dass das Ganze falsch ist.

Answer 1

Sie können clz/clo verwenden, um die Anzahl der führenden Nullen und Einsen zu zählen und damit die Anzahl der Einsen zu zählen. Die Idee ist, die führenden Nullen zu konsumieren, dann die führenden zu zählen (diese Bits aus dem Register zu verschieben), bis die Eingangsdaten Null sind.

d.h .:

li $t1, 0x4F044321 % $t1 Input number 
    srl $t1, $t1, 16 
    sll $t1, $t1, 16 % Discard least significant bits 
    li $t2, 0   % $t2 will hold number of 1s 
count: 
    beqz $t1, done  
    clz $t3, $t1 
    sllv $t1, $t1, $t3 
    clo $t3, $t1 
    addu $t2, $t2, $t3 
    sllv $t1, $t1, $t3 
    b count 
done: