获取位域中唯一位的数量

Question

我有一个 32 位位域，其中设置了一位。我怎样才能得到这个位的数量（如 int 或其他）？

示例（为简洁起见，使用 8 位）：

Input              Desired output
0x01 / 00000001 -> 0
0x04 / 00000100 -> 2
0x08 / 00001000 -> 3
0x00 / 00000000 -> undefined/whatever
0x06 / 00000110 -> undefined/whatever

我正在寻找简洁易读的代码或通用库函数，而不是最聪明或性能最好的解决方案。

Answer 1

您可以为此使用内置的编译器。 gcc 和 clang 支持这个：

Built-in Function: int __builtin_clz(unsigned int x)

Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.

int bit_index32(unsigned x) {
    return 31 - __builtin_clz(x);
}

对于更便携的解决方案，您可以使用一个简单的循环：

int bit_index32(unsigned x) {
    int n = 0;
    while (x > 1) { n++; x >>= 1; }
    return n;
}

更快的测试只有 5 个而不是最多 31 个：

int bit_index32(unsigned x) {
    int n = 0;
    if (x > 0xFFFF) { n += 16; x >>= 16; }
    if (x > 0xFF)   { n +=  8; x >>=  8; }
    if (x > 0xF)    { n +=  4; x >>=  4; }
    if (x > 0x3)    { n +=  2; x >>=  2; }
    if (x > 0x1)    { n +=  1; x >>=  1; }
    return n;
}

由于v是2的幂，索引是v-1中的位数，可以不用测试计算：

int bit_index32(unsigned v) {
    v--;
    v = v - ((v >> 1) & 0x55555555);
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
    return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}

另一个只适用于 2 的幂的无分支：

int bit_index32(unsigned v) {
    return !!(v & 0xAAAAAAAA)
         | !!(v & 0xCCCCCCCC) << 1
         | !!(v & 0xF0F0F0F0) << 2
         | !!(v & 0xFF00FF00) << 3
         | !!(v & 0xFFFF0000) << 4;
}

Sean Anderson 的 Bit Twiddling Hacks 更有趣！

Answer 2

一次移动一位，直到它处于低位，每次递增一个计数器。

int get_bit_num(uint32_t n)
{
    int count = 0;
    while (n>1) {
      n >>= 1;
      count++;
    }
    return count;
}

获取位域中唯一位的数量

Get number of sole bit in bitfield

c