c/c++语言开发共享计算位数的最快方法

如果您想手动编码，请尝试以下方法：

 #include  int popcnt8(uint8_t x) { x = (x & 0x55) + (x >> 1 & 0x55); x = (x & 0x33) + (x >> 2 & 0x33); x = (x & 0x0f) + (x >> 4 & 0x0f); return x; } 

在x86上，这编译为（AT＆T-syntax）：

 popcnt8: movl %edi, %eax shrb %dil andl $85, %eax andl $85, %edi addl %eax, %edi movl %edi, %eax shrb $2, %dil andl $51, %eax andl $51, %edi addl %eax, %edi movl %edi, %eax shrb $4, %dil andl $15, %eax addl %edi, %eax movzbl %al, %eax ret 

将此与gcc与内在函数生成的内容进行比较：

 #include  int popcnt8_intrin(uint8_t x) { return __builtin_popcount(x); } 

在带有SSE 4.2的x86上：

 popcnt8_intrin: movzbl %dil, %eax popcntl %eax, %eax ret 

这不是最佳的; clang生成：

 popcnt8_intrin: popcntl %edi,%eax ret 

将计算减少到一个（！）指令。

在没有SSE 4.2的x86上：

 popcnt8_intrin: subq $8, %rsp movzbl %dil, %edi call __popcountdi2 addq $8, %rsp ret 

gcc基本上在这里调用它的库。 不太理想。 clang做得更好：

 popcnt8_intrin: # @popcnt8_intrin movl %edi, %eax shrl %eax andl $85, %eax subl %eax, %edi movl %edi, %eax andl $858993459, %eax # imm = 0x33333333 shrl $2, %edi andl $858993459, %edi # imm = 0x33333333 addl %eax, %edi movl %edi, %eax shrl $4, %eax addl %edi, %eax andl $252645135, %eax # imm = 0xF0F0F0F imull $16843009, %eax, %eax # imm = 0x1010101 shrl $24, %eax ret 

clang计算整个32位数的popcnt。 这不是最佳的imho。

如果你没有做那么多的比较和分支，那么你的汇编程序代码会更快。

但显然，最快的方法是进行字节查找，特别是因为你只处理256个值（你可以使用朴素方法写一个值列表，然后只有一个static const table[256] = { ... }; return table[value];在你的函数中。

基准测试不同的解决方案。

如果汇编程序代码比编译器生成的代码慢，我不会感到惊讶！

编辑：通过执行以下操作，您的汇编代码会稍微快一点：

 int asmCount(int val) { int res = 0; asm volatile("begin:nt" "movl %1, %%ecxnt" "and $0x1, %%ecxnt" "addl %%ecx, %0nt" "shrl %1nt" "jnz beginnt" "end:" : "=r"(res) : "r" (val) : "ecx"); // Important: clobbers ecx! return res; } 

我删除了xor（res = 0无论如何应该这样做），然后比较（确定，如果val为零，我们执行一些额外的指令，但是对于任何高位设置，更糟糕的是，因为它是两个额外的指令每次迭代，意味着可能有16个额外的指令 – 其中一个是分支！），并在循环结束时将跳转更改为jnz。 它可能大致是编译器在第一种情况下生成的内容。 尝试在简单的代码上击败编译器并不容易！