NASM：指望有多少位在32位的數字設置爲1

Question

我有一個32位的數字，想算知道有多少位是1

我想這個僞代碼：

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

有沒有更高效的方法？

我在x86處理器上使用NASM。

（我只是用匯編開始，所以請不要告訴我從圖書館的extern使用的代碼，因爲我甚至不知道如何將它們;））

（我剛剛發現How to count the number of set bits in a 32-bit integer?這也包含我的解決方案。還有其他的解決方案發布，但不幸我似乎無法弄清楚，我怎麼會用匯編語言編寫它們）

Answer 1

最有效的方法（無論如何，就執行時間而言）查找表。顯然，你不會有一個40億條目表，但是你可以把32位分解成8位塊，只需要一個256條表，或者進一步分成4位塊，只需要16個條目。祝你好運！

Answer 2

我的x86彙編是有點生疏，但想到：

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包含您的位計數。

x86 shift instructions設置CF到最後一位移出，其中adc ecx, 0讀取它。

Answer 3

在具有SSE4支持的處理器中，您可以使用POPCNT指令爲您執行此操作。

最天真的算法實際上比你想象的要快（DIV指令真的很慢）。

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

關於你提到的有關以前的SO答案評論，我會在那裏舉個例子答案，並指導您如何我會轉換。

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; 
} 

（我假設你知道如何定義一個函數和有趣的東西）。 需要的是一個非常簡單的循環，一個計數器變量（傳統上，ecx既是索引也是計數器）和位測試指令。

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 

實施像組裝漢明權重算法並不複雜，但只是夠複雜了，你寧願不做爲初始作業的問題。

Answer 4

這個程序給你一個32位數的1。試試:)

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

使用BSF（位向前掃描）可能是一個有點比普通的換擋效率更高。

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: