计算位数的最快方法

可能重复:
如何计算32位整数中的设置位数?

给出一个unsigned char类型的值,计算它中的总位数。最快的方法是什么? 我写了三个函数,如下所示,最好的方法是什么,有人可以提出更快的一个吗?(我只想要非常快的一个)

const int tbl[] = { #define B2(n) n, n+1, n+1, n+2 #define B4(n) B2(n), B2(n+1), B2(n+1), B2(n+2) #define B6(n) B4(n), B4(n+1), B4(n+1), B4(n+2) B6(0), B6(1), B6(1), B6(2) }; char naivecount (unsigned char val) { char cnt = 0; while (val) { cnt += (val & 1); val = val >> 1; } return cnt; } inline tableLookUp(int val) { assert(val >= 0 && val <= 255); return tbl[val]; } int asmCount(int val) { int res = 0; asm volatile("xor %0, %0\n\t" "begin:\n\t" "cmp $0x0, %1\n\t" "jle end\n\t" "movl %1, %%ecx\n\t" "and $0x1, %%ecx\n\t" "addl %%ecx, %0\n\t" "shrl %1\n\t" "jmp begin\n\t" "end:" : "=r"(res) : "r" (val)); return res; } 

编辑:

我测试了所有的方法,最快的就是使用popcntl指令。在popcntl指令的平台上,我会使用表查找。

如果您想手动编码,请尝试以下方法:

 #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:\n\t" "movl %1, %%ecx\n\t" "and $0x1, %%ecx\n\t" "addl %%ecx, %0\n\t" "shrl %1\n\t" "jnz begin\n\t" "end:" : "=r"(res) : "r" (val) : "ecx"); // Important: clobbers ecx! return res; } 

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