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库中的代码,因为我甚至不知道如何包含它们;))

(我刚刚发现如何计算32位整数中的设置位数？这也包含我的解决方案.还有其他解决方案,但不幸的是我似乎无法弄清楚,我将如何在汇编程序中编写它们)

Answer 1

最有效的方法(无论如何,执行时间)是一个查找表.显然你不会有一个40亿的条目表,但你可以将32位分解成8位的块,只需要一个256条目的表,或者进一步分成4位的块,只需要16个条目.祝好运!

Answer 2

在具有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 3

我的 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 移位指令设置CF为移出的最后一位，adc ecx, 0读取它的位置。