我有一个长度为8的二进制数，例如00110101。其中有8个位被设置了。 我需要一个快速的位计数器来确定设置位的数量。 运行像这样的算法 x=x&(x-1) 将限制它包含的数字中设置的位数，但是我不太确定如何使用它。稍微帮助一下就好了！
7个回答
4
这个x=x&(x-1)可以从二进制字符串中去掉最低位的1。如果你在数字变成0之前计算去掉最低位的次数，你就可以得到被设置的位数。
char numBits(char x){
char i = 0;
if(x == 0)
return 0;
for(i = 1; x &= x-1; i++);
return i;
}
- Paul
3
执行x = x & (x-1)会删除掉最低位的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
允许的迭代次数将是给定数字中总位数。
- josh
1
问题描述中的方法（通常归因于K&R）的复杂度为n，其中n是数字中设置的位数。
通过使用额外的内存，我们可以将其带到O（1）：
使用位计数的查找表初始化一个查找表（编译时操作），然后引用它； 您可以在此处找到该方法：通过查找表计算位数
您可以在Henry S. Warren, Jr.（2007）的“加速人口统计的追求”中找到不同方法的详细讨论，精美代码 pp.147-158 O'Reilly
- vine'th
1
我有这段代码片段，仅适用于无符号整数：
希望这能帮到你。
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
- user12515980
0
根据您如何计算设置的位数 - 在我们的情况下，实际设置的位数为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;
}
（未经测试）
- glglgl
0
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。
- wecing
3
这看起来非常像上述专利。 - Hot Licks
@Daniel R Hicks。我希望这不是你的专利方法。上述方法也被描述为：“并行计算位集合”（Counting bits set in parallel），引用的参考文献早于你的专利申请。 - NealB
与大多数软件专利一样，魔鬼在于细节。律师们会添加足够的限定词来雕刻出一个“独特”的发明（尽管在这种情况下，我并不真的想要继续申请专利，但另一位发明人坚持要求）。然而，我已经撰写了几项相对自信的“干净”的专利，包括5,001,477-编码可变长度和空数据同时保留排序序列，我还有一些其他的专利被专利审查员明显地认为是“独特”和“新”的，但却被他们拒绝了。 - Hot Licks
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接