MSNA: Comptez le nombre de bits dans un nombre de 32 bits sont mis à 1

Question

J'ai un 32 numéro de Bit et que vous souhaitez compter savoir combien de bits sont 1.

Je pense à ce pseudo-code:

mov eax, [number] 
while(eax != 0) 
{ 
    div eax, 2 
    if(edx == 1) 
    { 
    ecx++; 
    } 
    shr eax, 1 
} 

Existe-t-il un moyen plus efficace? Je suis en utilisant NASM sur un processeur x 86.

(je suis juste en commençant par l'assembleur, donc s'il vous plaît ne me dites pas d'utiliser le code des bibliothèques externat, parce que je ne sais même pas comment les inclure;))

(Je viens de découvrir How to count the number of set bits in a 32-bit integer? qui a également contient ma solution.Il existe d'autres solutions publiées, mais malheureusement je n'arrive pas à comprendre, comment je les écrirais en assembleur)

Answer 1

Le moyen le plus efficace (en termes de temps d'exécution, de toute façon) est d'avoir un table de recherche. Évidemment, vous n'allez pas avoir une table d'entrée de 4 milliards, mais vous pouvez décomposer les 32 bits en morceaux de 8 bits et avoir seulement besoin d'une table de 256 entrées, ou plus bas en morceaux de 4 bits et seulement 16 entrées . Bonne chance!

Answer 2

Mon assembleur x86 est un peu rouillé, mais cela vient à l'esprit:

clc   ; clear carry 
xor ecx, ecx ; clear ecx 

shl eax, 1  ; shift off one bit into carry 
adc ecx, 0  ; add carry flag to ecx 
; ... repeat the last two opcodes 31 more times 

ecx contient votre nombre de bits.

x86 shift instructions définir CF sur le dernier bit décalé, où adc ecx, 0 le lit.

Answer 3

Dans les processeurs prenant en charge SSE4, vous disposez de l'instruction POPCNT pour vous.

L'algorithme le plus naïf est en réalité plus rapide que ce que vous avez imaginé (les instructions DIV sont vraiment lentes).

mov eax, [number] 
xor ecx,ecx 
loop_start: 
    test eax,1 
    jnz next 
    inc ecx 
next: 
    shr eax, 1 
    mov eax,ecx 

En ce qui concerne vos commentaires sur les réponses précédentes, je vais prendre un exemple de réponse à partir de là et vous guidera à travers la façon dont je vais le convertir.

long count_bits(long n) {  
    unsigned int c; // c accumulates the total bits set in v 
    for (c = 0; n; c++) 
    n &= n - 1; // clear the least significant bit set 
    return c; 
} 

(Je vais supposer que vous savez comment définir une fonction et des trucs amusants comme ça). Ce qui est nécessaire est une boucle très simple, une variable de compteur (traditionnellement, ecx est à la fois l'index et un compteur), et des instructions de test de bits.

mov edx,n 
    xor ecx,ecx 
loop_start: 
    test edx,edx 
    jz end 
    mov ebx,edx 
    dec ebx 
    and edx,ebx 
    inc ecx 
    jmp loop_start 
end: 
    mov eax,ecx 
    ret 

La mise en œuvre quelque chose comme l'algorithme de poids Hamming dans l'assemblage est pas compliqué, mais il est juste assez compliqué que vous préférez ne pas le faire comme un problème de travail initial.

Answer 4

Ce programme vous donne le nombre de 1 dans un nombre de 32 bits. Essayez :)

extern printf      
SECTION .data     
msg: db "The number of 1 bits are: %d",10,0 
inta1: dd 1234567 
num: dd 2147483647 
SECTION .text      

global main     
main:  
    mov eax, [num] 
    mov ecx,32 
    mov edx,0 
.loop: dec ecx 
    cmp ecx,0 
    jl .exit 
    shr eax,1 
    jnc .loop 
    inc edx 
jmp .loop 
.exit: 
    push edx 
    push dword msg   
    call printf    
    add  esp, 8 

Answer 5

 mov eax,[c] 
     xor ebx,ebx 
SSS: shr eax,1 ; after shift, if eax=0 ZF flag=1 
     jz XXX  ; end (no more bit on eax) 
     adc bl 
     jmp SSS 
XXX: adc bl 
     movb [Nbit],bl 

Answer 6

Utilisation de BSF (Bit balayage avant) est probablement un peu plus efficace que le déplacement ordinaire.

xor   edx,edx 
mov   eax,num 
bsf   ecx,eax 
je   end_bit_count 
; align? 
loop_bit_count: 
inc   ecx 
inc   edx 
shr   eax,cl 
bsf   ecx,eax 
jne   loop_bit_count 
end_bit_count: