可能重复:
如何计算 32 位整数中设置的位数?
给出一个无符号字符类型的值,计算其中的总位数。最快的方法是什么?我写了三个函数如下,最好的方法是什么,有人能想出一个更快的吗?(我只想要极快的)
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
指令。在没有指令的平台上,我将使用查表。