可能重复:
如何计算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, %0nt" "begin:nt" "cmp $0x0, %1nt" "jle endnt" "movl %1, %%ecxnt" "and $0x1, %%ecxnt" "addl %%ecx, %0nt" "shrl %1nt" "jmp beginnt" "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: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。 它可能大致是编译器在第一种情况下生成的内容。 尝试在简单的代码上击败编译器并不容易!
以上就是c/c++开发分享计算位数的最快方法相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/559990.html