c - 汉明重量(数字中1的个数)混合C与组件

Question

我正在尝试计算数组中有多少个数字 1。

首先我有一个 C 语言的代码(工作正常):

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 循环转换为程序集。我写了一些代码，但结果不正确。(我是汇编世界的新手)

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

我在 Intel 处理器上使用 GCC(在 Linux 上)。

Answer 1

您从一个非常低效的算法开始 - 如果您使用更好的算法，那么您可能不需要在汇编程序上浪费时间。参见 Hacker's Delight和/或 Bit Twiddling Hacks以获得更有效的方法。

还要注意较新的 x86 CPU 有一个 POPCNT在一条指令中完成上述所有操作的指令(你也可以 call it via an intrinsic，所以不需要 asm)。

最后 gcc 有一个内置函数:__builtin_popcount ，这又能满足您的所有需求——它将在较新的 CPU 上使用 POPCNT，在较旧的 CPU 上使用等效的 asm。