使用 C 计算 8 位二进制数中的设置位数

Question

我有一个长度为 8 的二进制数，例如 00110101 有 8 位设置。

我需要快速位计数来确定设置位的数量，即 popcount 又名人口计数。 像这样运行算法 x=x&(x-1) 会将其限制为数字包含的设置位数，但我不太确定如何使用它。

与 计算设置位数不同在 32 位整数中，我只有 8 位整数，因此 O(log width) bithack 方法仍然有几个步骤，可能不会比 O(set_bits) 或 4 位或CPU 上的 8 位查找表没有硬件 popcount，或者以无法接受假设支持的方式进行编译。

Answer 1

此 x=x&(x-1) 从二进制字符串中删除最低设置位。如果计算在数字变为 0 之前删除最低位的次数，您将得到已设置的位数。

char numBits(char x){
    char i = 0;
    if(x == 0)
        return 0;
    for(i = 1; x &= x-1; i++);
    return i;
}

Answer 2

执行 x = x & (x-1) 将删除最低位集。因此，在您的情况下，迭代将执行为，

loop #1: 00110101(53) & 00110100(52) = 00110100(52) :: num bits = 1

loop #2: 00110100(52) & 00110011(51) = 00110000(48) :: num bits = 2

loop #3: 00110000(48) & 00101111(47) = 00100000(32) :: num bits = 3

loop #3: 00100000(32) & 00011111(31) = 00000000( 0) :: num bits = 4

允许的迭代次数将是给定数字中的总位数。

Answer 3

美国专利 6,516,330 – 计算数据字中的设置位

（我只是发明了它 - 不要不要让我解释。）

Answer 4

问题中描述的方法（通常归因于 K&R ）的复杂度为 n，其中 n 是数字中设置的位数。

通过使用额外的内存，我们可以将其变为 O(1)：

使用位数（编译时操作）初始化查找表，然后引用它；
您可以在这里找到该方法：计数由查找表设置的位数

您可以找到Henry S. Warren, Jr.(2007)“The Quest for an Accelerated Population Count”中对不同方法的详细讨论，美丽的代码 pp.147-158奥莱利

Answer 5

我的代码片段仅适用于无符号整数：
希望这有帮助。

uint G = 8501; //10 0001 0011 0101
uint g = 0;

for (int i = 0; i < 32; i++)
{
  g += (G << (31 - (i % 32))) >> 31;
}

Console.WriteLine(g); //6

Answer 6

根据您计算设置位的方式 - 在我们的例子中，实际设置位的数量为 4；位宽（我在此将其定义为最高位组的数字加 1）为 6（因为您需要 6 位来表示您的数字）。后一个可以通过

char highestbit (uint32_t num)
{
    char i;
    for (i = 0; i < sizeof(num)*8; i++) {
        if ((1L << i) > num) {
            return i;
        }
    }
    return sizeof(num)*8;
}

（未经测试）确定

Answer 7

x := (x and $55555555) + ((x shr 1) and $55555555); 
x := (x and $33333333) + ((x shr 2) and $33333333); 
x := (x and $0F0F0F0F) + ((x shr 4) and $0F0F0F0F); 
x := (x and $00FF00FF) + ((x shr 8) and $00FF00FF); 
x := (x and $0000FFFF) + ((x shr 16) and $0000FFFF);

摘自matrix67的博客，是中文的。