在C中查找位掩码中的设置位位置的最佳方法
这个问题在这里已经有了答案：
来自Hacker's Delight的算法（书）：
int count_bits(long long s)
{
s = (s&0x5555555555555555L) + ((s>>1)&0x5555555555555555L);
s = (s&0x3333333333333333L) + ((s>>2)&0x3333333333333333L);
s = (s&0x0F0F0F0F0F0F0F0FL) + ((s>>4)&0x0F0F0F0F0F0F0F0FL);
s = (s&0x00FF00FF00FF00FFL) + ((s>>8)&0x00FF00FF00FF00FFL);
s = (s&0x0000FFFF0000FFFFL) + ((s>>16)&0x0000FFFF0000FFFFL);
s = (s&0x00000000FFFFFFFFL) + ((s>>32)&0x00000000FFFFFFFFL);
return (int)s;
}
除了已经解释过的好点儿，还有其他选择。
这假设你有x86（64），SSE4，gcc并且可以使用-msse4开关编译，你可以使用：
int CountOnesSSE4(unsigned int x)
{
return __builtin_popcount(x);
}
这将编译成单一的popcnt指令。 如果你需要快速代码，你可以在运行时检查SSE，并使用最好的功能。
如果你希望数字的数量少一些，这可能也很快（并且总是比通常的移位和比较循环更快）：
int CountOnes(unsigned int x)
{
int cnt = 0;
while (x) {
x >>= ffs(x);
cnt++;
}
return cnt;
}
在x86上（即使没有SSE），ffs将编译成单指令（bsf），并且循环的数目将取决于数目。
你可能会这样做：
long long bit_mask = 0xdeadbeefdeadbeef;
int i;
for (i = 0; i < (sizeof(long long) * 8); i++) {
int res = bit_mask & 1;
printf ("Pos %i is %in", i, res);
bit_mask >>= 1;
}
上一篇: Best method to find out set bit positions in a bit mask in C