代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
当前回答
#!/user/local/bin/perl
$c=0x11BBBBAB;
$count=0;
$m=0x00000001;
for($i=0;$i<32;$i++)
{
$f=$c & $m;
if($f == 1)
{
$count++;
}
$c=$c >> 1;
}
printf("%d",$count);
ive done it through a perl script. the number taken is $c=0x11BBBBAB
B=3 1s
A=2 1s
so in total
1+1+3+3+3+2+3+3=19
其他回答
int countBits(int x)
{
int n = 0;
if (x) do n++;
while(x=x&(x-1));
return n;
}
或者:
int countBits(int x) { return (x)? 1+countBits(x&(x-1)): 0; }
在我最初的回答7年半之后,@PeterMortensen质疑这是否是有效的C语法。我发布了一个在线编译器的链接,显示它实际上是完全有效的语法(代码如下)。
#include <stdio.h>
int countBits(int x)
{
int n = 0;
if (x) do n++; /* Totally Normal Valid code. */
while(x=x&(x-1)); /* Nothing to see here. */
return n;
}
int main(void) {
printf("%d\n", countBits(25));
return 0;
}
输出:
3
如果你想重新写清楚,它看起来是这样的:
if (x)
{
do
{
n++;
} while(x=x&(x-1));
}
但在我看来,这太过分了。
然而,我也意识到函数可以变得更短,但可能更神秘,写为:
int countBits(int x)
{
int n = 0;
while (x) x=(n++,x&(x-1));
return n;
}
你要找的函数通常被称为二进制数的“横向和”或“总体数”。Knuth在前分册1A,第11-12页中讨论了它(尽管在第2卷,4.6.3-(7)中有简要的参考)。
经典文献是Peter Wegner的文章“二进制计算机中的一种计数技术”,摘自ACM通讯,卷3(1960)第5号,第322页。他给出了两种不同的算法,一种针对“稀疏”(即1的数量很少)的数字进行了优化,另一种针对相反的情况。
另一个汉明权重算法,如果你使用的是BMI2 CPU:
the_weight = __tzcnt_u64(~_pext_u64(data[i], data[i]));
我使用下面的函数。我还没有检查基准测试,但它是有效的。
int msb(int num)
{
int m = 0;
for (int i = 16; i > 0; i = i>>1)
{
// debug(i, num, m);
if(num>>i)
{
m += i;
num>>=i;
}
}
return m;
}
从Python 3.10开始,你将能够使用int.bit_count()函数,但目前,你可以自己定义这个函数。
def bit_count(integer):
return bin(integer).count("1")