我正在尝试计算数组中的数字1有多少。
首先，我有一个 C lenguaje 的代码（工作正常）：
int popcount2(int* array, int len){
int i;
unsigned x;
int result=0;
for (i=0; i<len; i++){
x = array[i];
do{
result+= x & 0x1;
x>>= 1;
} while(x);
}
return result;
}
现在我需要使用 3-6 行代码将 do-while 循环转换为 Assembly。我写了一些代码，但结果不正确。（我是组装界的新手）
int popcount3(int* array, int len){
int i;
unsigned x;
int result=0;
for (i=0; i<len; i++){
x = array[i];
asm(
"ini3: n"
"adc $0,%[r] n"
"shr %[x] n"
"jnz ini3 n"
: [r]"+r" (result)
: [x] "r" (x) );
}
}
我正在使用带有英特尔处理器的GCC（在Linux上）。
你从一个非常低效的算法开始 - 如果你使用更好的算法，那么你可能不需要浪费时间在汇编器上。请参阅黑客的喜悦和/或比特摆动黑客，了解更有效的方法。
另请注意，较新的 x86 CPU 具有 POPCNT 指令，该指令在一个指令中执行上述所有操作（您也可以通过内部函数调用它，因此不需要 asm）。
最后 gcc 有一个内置的： __builtin_popcount ，它再次满足您的所有需求 - 它将在较新的 CPU 上使用 POPCNT，在较旧的 CPU 上使用等效的 asm。
当我需要创建一个popcount时，我最终使用了@PaulR提到的Bit Twiddling Hacks中的5和3方法。 但是，如果我想用循环来做到这一点，也许是这样的：
#include <stdio.h>
#include <stdlib.h>
int popcount2(int v) {
int result = 0;
int junk;
asm (
"shr $1, %[v] nt" // shift low bit into CF
"jz done n" // and skip the loop if that was the only set bit
"start: nt"
"adc $0, %[result] nt" // add CF (0 or 1) to result
"shr $1, %[v] nt"
"jnz start n" // leave the loop after shifting out the last bit
"done: nt"
"adc $0, %[result] nt" // and add that last bit
: [result] "+r" (result), "=r" (junk)
: [v] "1" (v)
: "cc"
);
return result;
}
int main(int argc, char *argv[])
{
for (int x=0; x < argc-1; x++)
{
int v = atoi(argv[x+1]);
printf("%d %dn", v, popcount2(v));
}
}
adc几乎总是比在 CF 上分支更有效。
"=r" (junk) 是一个虚拟输出操作数，与 v（"1"约束）位于同一寄存器中。 我们使用它来告诉编译器 asm 语句会破坏v输入。 我们本可以使用[v] "+r"(v)来获取读写操作数，但我们不希望更新 C 变量v。
请注意，此实现的环路跳闸计数是最高设置位的位置。 （bsr或32 - clz(v)）。 @rcgldr 的实现每次迭代清除最低设置位，当设置位数较低但并非全部接近整数底部时，通常会更快。
使用 3-6 行代码进行组装。
此示例使用 4 指令循环：
popcntx proc near
mov ecx,[esp+4] ;ecx = value to popcnt
xor eax,eax ;will be popcnt
test ecx,ecx ;br if ecx == 0
jz popc1
popc0: lea edx,[ecx-1] ;edx = ecx-1
inc eax ;eax += 1
and ecx,edx ;ecx &= (ecx-1)
jnz short popc0
popc1: ret
popcntx endp
此示例使用 3 指令循环，但在大多数处理器上，它比 4 指令循环版本慢。
popcntx proc near
mov eax,[esp+4] ;eax = value to popcnt
mov ecx,32 ;ecx = max # 1 bits
test eax,eax ;br if eax == 0
jz popc1
popc0: lea edx,[eax-1] ;eax &= (eax-1)
and eax,edx
loopnz popc0
popc1: neg ecx
lea eax,[ecx+32]
ret
popcntx endp
这是一个替代的非循环示例：
popcntx proc near
mov ecx,[esp+4] ;ecx = value to popcnt
mov edx,ecx ;edx = ecx
shr edx,1 ;mov upr 2 bit field bits to lwr
and edx,055555555h ; and mask them
sub ecx,edx ;ecx = 2 bit field counts
; 0->0, 1->1, 2->1, 3->1
mov eax,ecx
shr ecx,02h ;mov upr 2 bit field counts to lwr
and eax,033333333h ;eax = lwr 2 bit field counts
and ecx,033333333h ;edx = upr 2 bit field counts
add ecx,eax ;ecx = 4 bit field counts
mov eax,ecx
shr eax,04h ;mov upr 4 bit field counts to lwr
add eax,ecx ;eax = 8 bit field counts
and eax,00f0f0f0fh ; after the and
imul eax,eax,01010101h ;eax bit 24->28 = bit count
shr eax,018h ;eax bit 0->4 = bit count
ret
popcntx endp
你能做的最好的想法是按照Paul R的建议使用内置popcount函数，但由于你需要用汇编形式编写它，这对我有用：
asm (
"start: n"
"and %0, %1 n"
"jz end n"
"shr $0, %1 n"
"jnc start n"
"inc %1 n"
"jmp start n"
"end: n"
: "+g" (result),
"+r" (x)
:
: "cc"
);
在前两行，您只需检查x的内容（如果为零Jump Zero，则转到结尾）。然后你x向右移动一点，然后：
在移位操作结束时，
CF标志包含移出目标操作数的最后一位。
如果没有设置CF，只需转到开始（Jump Not Carry）否则递增结果，然后转到开始。
关于组装的美好想法是，你可以用很多方式做事......
asm (
"start: n"
"shr $1, %1 n"
"jnc loop_cond n"
"inc %0 n"
"and %1, %1 n"
"loop_cond: n"
"jnz start n"
: "+g" (result),
"+r" (x)
:
: "cc"
);
在这里，您再次使用SHift Right指令，如果没有CF，只需转到循环条件。
否则再次递增结果并调用二进制AND（INC确实会修改ZF）。
使用LOOP和ECX
我很好奇如何在 3 个指令中做到这一点（我认为如果不可能，你的老师不会给你 3 的最低限制），我意识到 x86 也有LOOP指令：
每次执行 LOOP 指令时，计数寄存器都会递减，然后检查 0。如果计数为 0，则循环终止，程序执行继续执行 LOOP 指令之后的指令。如果计数不为零，则对目标（目标）操作数执行接近跳转，这可能是循环开始时的指令。*
您可以使用 GCC 输入约束添加输入参数：
c-c寄存器。
asm (
"start: n"
"shr $1, %1 n"
"adc $0, %0 n"
"loop start n"
: "+g" (result)
: "r" (x),
"c" (8) // Assuming 8b type (char)
);
只是为了确保它编译为正确的汇编：
0x000000000040051f <+25>: mov $0x8,%ecx
0x0000000000400524 <+30>: mov -0x8(%rbp),%eax
0x0000000000400527 <+33>: shr %edx
0x0000000000400529 <+35>: adc $0x0,%eax
0x000000000040052c <+38>: loop 0x400527 <main+33>
我认为第一个应该有更好的性能，特别是如果只设置了 1 位，这种方法总是k*8迭代。
上交所4和单指令
我知道你必须使用循环，但只是为了好玩......使用SSE4扩展，您只需一条指令即可完成此操作POPCNT：
此指令计算在第二个操作数（源）中设置为 1 的位数，并返回第一个操作数（目标寄存器）中的计数。
*
我想（我的笔记本上有一个相当旧的CPU，所以我无法为您测试）您应该只需一条简单的指令即可完成此操作：
asm (
"POPCNT %1, %0 n"
: "=r" (result)
: "mr" (x)
: "cc"
);
（如果您尝试此操作并且确实有SSE4扩展，请告诉我它是否有效）
性能
我测量了进行100，000，000次流行计数所需的时间，将我的第一和第二种方法与David Wohlferd的方法进行了比较。[原始数据]
+--------------+------------+------------+------------+
| | 0x00000000 | 0x80000001 | 0xffffffff |
+--------------+------------+------------+------------+
| 1st solution | 0.543 | 5.040 | 3.833 |
| LOOP | 11.530 | 11.523 | 11.523 |
| Davids | 0.750 | 4.893 | 4.890 |
+--------------+------------+------------+------------+
如果有人可以将这 3 个与 SSE4 的POPCNT指令进行比较，我会很高兴。