我有一个 32 位数字，想知道有多少位是 1。
我在想这个伪代码：
mov eax, [number]
while(eax != 0)
{
div eax, 2
if(edx == 1)
{
ecx++;
}
shr eax, 1
}
有没有更有效的方法？
我在 x86 处理器上使用 NASM。
（我刚开始使用汇编程序，所以请不要告诉我使用外部库中的代码，因为我什至不知道如何包含它们；））
（我刚刚发现如何计算 32 位整数中的设置位数？其中也包含我的解决方案。发布了其他解决方案，但不幸的是我似乎无法弄清楚，我将如何在汇编程序中编写它们）
在支持 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
在汇编中实现诸如汉明权重算法之类的东西并不复杂，但已经足够复杂了，以至于您不希望将其作为初始作业问题进行。
最有效的方法（无论如何就执行时间而言）是有一个查找表。显然你不会有一个 40 亿的条目表，但你可以将 32 位分解为 8 位块，只需要一个 256 位表，或者进一步分解为 4 位块，只需要 16 个条目. 祝你好运！
我的 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读取它。
作为记录，如果您想要良好的性能，您通常希望避免循环/分支，使用 8 位表查找或乘法 bithack（GCC 的当前标量回退为__builtin_popcntwithout -mpopcnt）。如果您的数字通常很小（右移 1），或者您的数字通常只设置了几个位（循环使用 清除最低设置位x & (x-1)），则循环几乎没问题。但是对于设置了一半或更多位的数字，这些性能相当差。
大多数现代 x86 CPU 支持popcnt 指令。它由 SSE4.2 隐含，但也有自己的 CPUID 功能位，因此 CPU 可以在没有 SSE4.2 的情况下拥有它。英特尔酷睿 2 及更早版本没有此功能。
xor eax,eax ; avoid false dependency on Sandybridge-family before IceLake
popcnt eax, edi
如果你不介意覆盖同一个寄存器，popcnt edi, edi例如避免输出错误依赖的危险：你已经对同一个寄存器有一个真正的依赖。（为什么打破 LZCNT 的“输出依赖”很重要？）
如果没有 HW popcnt，另一个选项是 SSSE3pshufb，它实际上非常适合计算大型数组，特别是如果您有 AVX2。看
movzx ecx, al可以进行数组查找，使用/ movzx edx, ah/等提取每个字节shr eax, 16。然后movzx ecx, [table + rcx]/ add cl, [table + rdx]。请注意，总结果最多为 64，因此不会溢出 8 位寄存器。这需要一个 256 字节的表才能在高速缓存中保持热状态以获得良好的性能。如果你做了很多popcnt但不能使用SIMD，这可能是一个不错的选择；针对您的用例将其与 bithack 进行基准测试。
来自https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel /如何计算 32 位整数中设置位的数量？如果在编译时未启用 HW popcnt，则 GCC 当前使用的是什么。（即在 libgcc 辅助函数中）。请参阅该答案以了解 bithack 如何/为什么将位求和到 2 位累加器，然后再水平到 4 位等。（有趣的事实：GCC 和 clang 实际上将 C 逻辑识别为 popcnt 习语并将其编译为带有. 的popcnt指令-mpopcnt。以下 asm 是没有-mpopcnt 的GCC -O3 输出 ；我看不到任何手动改进它的方法。它尽可能使用 EAX 作为 AND 的目的地，以允许没有 modrm 的短格式字节。）and eax, imm32
此非分支代码不需要任何数据查找，因此它不会缓存未命中（I-cache 除外），如果您关心 popcount 性能（尤其是延迟）但不经常这样做，可能会很好足以使查找表在缓存中保持热状态。（或者对于 64 位整数，64 位版本可能甚至比 8x 字节查找更好。）
; x86-64 System V calling convention
; but also of course works for 32-bit mode with the arg in a register
numberOfSetBits: ; 32-bit unsigned int x in EDI
mov eax, edi
shr eax, 1
and eax, 0x55555555 ; (x>>1) & 0x55555555
sub edi, eax ; x -= ((x>>1) & 0x55555555) 2-bit sums
mov eax, edi
shr edi, 0x2
and eax, 0x33333333
and edi, 0x33333333
add edi, eax ; pairs of 2-bit accumulators -> 4
mov eax, edi
shr eax, 0x4
add eax, edi ; we can add before masking this time without overflow risk
and eax, 0x0f0f0f0f
imul eax, eax, 0x01010101 ; sum the 4 bytes into the high byte (because their values are small enough)
shr eax, 24
ret
对于 64 位整数，它是相同的序列，以 64 位乘法结束。（但您需要mov reg, imm64具体化 64 位掩码和乘法器常量；它们不能作为 AND 或 IMUL 的立即数）。
RORX 之类的指令可能有助于更有效地复制和移位而不是 mov/shr，但是任何具有 RORX 的 CPU 也将具有 POPCNT，因此您应该使用它！LEA 到复制和左移无济于事：加法将进位从低位传播到高位，因此为避免在第一步丢失顶部的位，您需要右移。该>>2步骤也不能添加到每对 2 位累加器中的较高者：该点的最大和是4，并且需要 3 位来表示，因此最高的累加器（在寄存器的顶部）可能会丢失如果你做了计数lea eax, [rdi + rdi]/ 2x 和 / add，因为不是 4 位未对齐，而是只有 2。而且您最终需要右移以在 imul 之前的某个时间点将计数器放回其字节的底部，因此您会延长关键即使可以在前面的步骤中使用左移/添加，路径延迟也是如此。
有三个主要选择：
add same,same或右移shr）并添加移出的位。如果设置的位通常集中在高端或低端，那么寄存器在远少于 32 次迭代后变为零，但这仍然是最坏的情况。x &= x-1并计算多少次迭代变为零。如果总共设置的位很少，那么不好。（或者如果你不是首先输入，如果清除位很少。或者可能有一个设置最低零位的位黑客，比如x |= x+1可能？）。最坏的情况仍然是 32 次迭代，其 dep 链比仅移位更长。对于小代码大小（但不是速度），汉明权重（数字中的 1 的数量）将 C 与汇编混合显示的循环非常好。它的 NASM 版本如下所示：
;;; Good for small inputs (all set bits near the bottom)
;; input: EDI (zeroed when we're done)
;; output: EAX = popcnt(EDI)
popcount_shr_loop:
xor eax, eax
; optional: make the first adc non-redundant by peeling the first iteration. Otherwise just fall into the loop (with CF=0 from xor)
shr edi, 1 ; shift low bit into CF
;; jz .done ; not worth running an extra instruction for every case to skip the loop body only for the input == 0 or 1 case
.loop:
adc eax, 0 ; add CF (0 or 1) to result
shr edi, 1
jnz .loop ; leave the loop after shifting out the last bit
;.done:
adc eax, 0 ; and add that last bit
ret
如果您输入中的设置位可能接近顶部，请使用add edi, edi而不是shr，因为它设置了我们关心的 FLAGS shl。 add可以与jccSandybridge-family 进行宏融合，所以这实际上略好于shr; 如果循环退出分支预测正确，则对超线程更友好，ROB 中的微指令更少，因此 OoO exec 可以看到更远的地方。或者，如果较早的缓存未命中或某些事情仍在拖延退休，则可以更快地进入循环。
对于更小的代码大小，您可以shr在进入循环之前跳过，因此第一个adc是多余的。（异或归零清除 CF）。
@spoulson 的回答建议展开循环 32 次（没有 jz .done）。当您想要一个大的直线代码块以获得具有任意位模式的最大速度时，以乘法结尾的 bithack 移位/和/加法会更好。 adc reg,0在大多数 CPU 上是 1 uop，除了 Intel P6 系列（PPro 到 Nehalem）（0在Broadwell 之前是 Intel SnB 系列的一个特例）。无论如何，与 15-uop bithack 相比，64 uop 和 32 周期延迟仍然很糟糕，因此完全展开它会比其他策略更糟糕。
但是，将其展开 2 或 4 可能是一个中间立场。这将使不同的输入以相同的方式分支，例如，其设置位在低 4 位的每个输入将通过循环一次，而分支不被采用。
popcount_shr_loop_unroll2:
xor eax, eax
shr edi, 1 ; shift low bit into CF
;; jz .done ; still optional, but saves more work in the input <= 1 case. Still not worth it unless you expect that to be very common.
.loop:
%rep 2 ;; Unroll
adc eax, 0 ; add CF (0 or 1) to result
shr edi, 1
%endrep ;; still ending with ZF and CF set from a shift
jnz .loop ; leave the loop on EDI == 0
;.done:
adc eax, 0 ; there may still be a bit we haven't added yet
ret
您可以尝试通过将/作为循环分支来让无序的 exec 更快地看到循环退出条件，并让循环体将 EDI 复制到另一个寄存器并一次移出低 4 位 1。但那时你可能只想要 bithack 版本；具有 OoO exec 的 x86 CPU 也具有快速 imul r32，例如 Pentium II/III 上的 4 个周期延迟，AMD K8 及更高版本上的 3 个周期，以及自 Core 2 以来的 Intel。它们的代码获取/解码能力应该处理涉及 32 个更大的指令-位掩码常数足够好。shr edi, 4jnz
（因为我们正在考虑旧 CPU：在 P5 Pentium 上，shr并且adc都只能在 U 管道中运行，所以展开不会让它们相互配对以利用 ILP。如果你曾经add移动高位但是，进入 CR，因为add可以在 U 或 V 管道中运行。）
另一个展开选项是分成两半，高一半出顶部，低一半出底部。（如果您关心延迟，也可以累积到单独的计数器中，否则它仍然可以帮助 OoO exec 更快地找到循环退出。但是测试两半为零会变得笨拙；也许mov ecx, ebx// add ecx, edx。ADDjnz可以与 jnz 进行宏融合SnB 系列，与 OR 不同。或者使用 LEA / TEST+JNZ，AMD Zen 和 Intel 上的 2 个前端 uops。）
lea edx, [rdi-1]另一个选项是在/上循环and edi, edx（清除最低设置位，如果 ZF 变为零，则设置 ZF）。这对于只有几个设置位的数字是可以的。
;; could be good if very few bits are set, even if they're scattered around
;; Input: EDI (zeroed when done)
;; output: EAX = popcount(EDI)
;; clobbers: EDX
popcount_loop_lsr:
xor eax,eax
test edi,edi
jz .done ; if(!x) return 0;
.loop: ; do{
inc eax ; ++count
lea edx, [rdi-1]
and edi, edx ; x &= x-1 clear lowest set bit
jnz .loop ; }while(x)
.done:
ret
有关更多类似的 bithacks x & (x-1)，请参阅https://catonmat.net/low-level-bit-hacks。另请注意，BMI1 指令blsr会执行此操作，因此当您已经打开 x86 指令参考时，这是一个方便的地方，可以作为公式的提醒进行检查。但当然，如果你有 BMI1，你就会有popcnt. popcnt 实际上有它自己的特性位，但是现实世界中没有任何 CPU 具有 BMI1 但没有 popcnt/SSE4.2。
请注意，这通过 LEA 和 AND 具有 2 周期循环依赖，这与另一个循环中通过 SHR 和 ADC（假设单 uop ADC）的 1 周期依赖不同。所以每次迭代都有两倍的数据依赖。但从好的方面来说，我们只是循环设置位，跳过零。尽管如此，最坏的情况 ( EDI=-1) 有两倍的延迟。
and/jnz实际上可以将英特尔 SnB 系列宏融合为单个和分支 uop。（因为它就像test）。所以每次迭代仍然只有 3 个前端 uops，但分支错误预测不太可能很快被检测到，所以就整体前端成本而言，这个版本可能很糟糕。
因为inc eax只是计算循环迭代，没有数据依赖于x更新逻辑，展开仍然需要一个分支，我认为，除非你在循环之后做了一些额外的逻辑来检查中间临时是否已经为零。由于x &= x-1;dep 链是关键路径，展开可能没有帮助。
（如果您想找到每个设置位的位置并将其存储到数组中，如果您有单独的有效方法来弹出计数，则可以展开超调，如@aqrit 在另一个问答中的回答）
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
该程序为您提供 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
使用 bsf (Bit Scan Forward) 可能比普通移位更有效。
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:
mov eax,dword [number]; we store the number in eax
mov ecx,1
mov edx,0
loop_1:
cmp eax,0 ;we compare the number with 0
je endl_loop ;when the number is zero we exit the loop
test eax,01h ;is the last bit equal to 1?
jpe the_bit_is_zero ;jump if parity is even=the bit is zero
inc edx ;we found another 1 digit
the_bit_is_zero:
inc ecx ;we continue the loop
shr eax,1 ;shift the bits to right =nr/2
loop loop_1
endl_loop:
;the result is stored in edx
最好的方法：
tabx:array [0..255] of byte = //number of bit for each byte (COPY THIS TABLE)
(0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8);
In MASM:
asm
mov eax,number //32 bit
movzx ecx,tabx[al] //for clear ecx except cl
addb cl,tabx[ah] //add ah to cl
shr eax,16 //put left part in ah-al
addb cl,tabx[al]
addb cl,tabx[ah]
mov result,ecx