我有一个长度为8的二进制数,例如00110101。其中有8个位被设置了。 我需要一个快速的位计数器来确定设置位的数量。 运行像这样的算法 x=x&(x-1) 将限制它包含的数字中设置的位数,但是我不太确定如何使用它。稍微帮助一下就好了!
我有一个长度为8的二进制数,例如00110101。其中有8个位被设置了。 我需要一个快速的位计数器来确定设置位的数量。 运行像这样的算法 x=x&(x-1) 将限制它包含的数字中设置的位数,但是我不太确定如何使用它。稍微帮助一下就好了!
这个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;
}
执行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
问题描述中的方法(通常归因于K&R)的复杂度为n,其中n是数字中设置的位数。
通过使用额外的内存,我们可以将其带到O(1):
使用位计数的查找表初始化一个查找表(编译时操作),然后引用它; 您可以在此处找到该方法:通过查找表计算位数
您可以在Henry S. Warren, Jr.(2007)的“加速人口统计的追求”中找到不同方法的详细讨论,精美代码 pp.147-158 O'Reilly
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
根据您如何计算设置的位数 - 在我们的情况下,实际设置的位数为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;
}
(未经测试)
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。