Best method to find out set bit positions in a bit mask in C

This question already has an answer here:

How to count the number of set bits in a 32-bit integer? 50 answers

---

来自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;
}

---

Besides already explained nice bit twiddling hacks, there are other options.

This assumes that you have x86(64), SSE4, gcc and compile with -msse4 switch you can use:

int CountOnesSSE4(unsigned int x)
{
    return __builtin_popcount(x);
}

This will compile into single popcnt instruction. If you need fast code you can actually check for SSE at runtime and use best function available.

If you expect number to have small number of ones, this could also be fast (and is always faster than the usual shift and compare loop):

int CountOnes(unsigned int x)
{
    int cnt = 0;
    while (x) {
        x >>= ffs(x);
        cnt++;
    }
    return cnt;
}

On x86 (even without SSE) ffs will compile into single instruction (bsf), and number of loops will depend on number of ones.

---

你可能会这样做：

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;

}

链接地址: http://www.djcxy.com/p/72600.html

上一篇: 对仅使用按位运算设置的位数进行计数

下一篇: 在C中查找位掩码中的设置位位置的最佳方法