如果您想手动编码,请尝试以下操作:
#include <stdint.h>
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 语法):
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 <stdint.h>
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。恕我直言,这不是最佳的。