可能是重复问题:
如何计算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
指令。在没有该指令的平台上,我将使用查表法。
popcount
。 - Jens Gustedt