如何检查8位无符号字符中的设置位数？

Question

所以我必须在C中找到unsigned char变量的设置位(在1上)？

类似的问题是如何计算32位整数中的设置位数？但它使用的算法不易适应8位无符号字符(或不明显).

Answer 1

对于 8 位变量，最快的方法是使用查找表。

构建一个包含 256 个值的数组，每个 8 位组合一个。每个值应包含其相应索引中的位数：

int bit_count[] = {
// 00 01 02 03 04 05 06 07 08 09 0a, ... FE FF
    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, ..., 7, 8
};

获取组合的计数与从数组中查找值相同bit_count。这种方法的优点是速度非常快。

您可以使用一个简单的程序生成数组，该程序以缓慢的方式一位一位地计数：

for (int i = 0 ; i != 256 ; i++) {
    int count = 0;
    for (int p = 0 ; p != 8 ; p++) {
        if (i & (1 << p)) {
            count++;
        }
    }
    printf("%d, ", count);
}

（生成表格的演示）。

如果您想用一些 CPU 周期换取内存，可以使用 16 字节查找表进行两个 4 位查找：

static const char split_lookup[] = {
    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4
};

int bit_count(unsigned char n) {
    return split_lookup[n&0xF] + split_lookup[n>>4];
}

演示。

Answer 2

问题中建议的算法如何计算32位整数中的设置位数？很容易适应8位:

int NumberOfSetBits( uint8_t b )
{
     b = b - ((b >> 1) & 0x55);
     b = (b & 0x33) + ((b >> 2) & 0x33);
     return (((b + (b >> 4)) & 0x0F) * 0x01);
}

它只是将常数缩短为最低有效8位,并删除最后24位右移的情况.同样,它可以使用8位移位适应16位.注意,在8位的情况下,32位算法的机械适应导致冗余* 0x01,这可以省略.