代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
当前回答
这不是最快或最好的解决方案,但我以自己的方式发现了同样的问题,我开始反复思考。最后我意识到它可以这样做,如果你从数学方面得到这个问题,画一个图,然后你发现它是一个有周期部分的函数,然后你意识到周期之间的差异……所以你看:
unsigned int f(unsigned int x)
{
switch (x) {
case 0:
return 0;
case 1:
return 1;
case 2:
return 1;
case 3:
return 2;
default:
return f(x/4) + f(x%4);
}
}
其他回答
我特别喜欢这个来自《财富》的例子:
#define BITCOUNT(x) (((BX_(x)+(BX_(x)>>4)) & 0x0F0F0F0F) % 255) #define BX_(x) ((x) - (((x)>>1)&0x77777777) - (((x)>>2)&0x33333333) - (((x)>>3)&0x11111111))
我最喜欢它,因为它太漂亮了!
我总是在竞争性编程中使用它,它很容易写,而且效率很高:
#include <bits/stdc++.h>
using namespace std;
int countOnes(int n) {
bitset<32> b(n);
return b.count();
}
为什么不迭代地除以2呢?
count = 0 while n > 0 if (n % 2) == 1 count += 1 n /= 2
我同意这不是最快的,但是“最好”这个词有点含糊不清。我认为“最好”应该有一个清晰的元素
#!/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
这是在golang中的实现
func CountBitSet(n int) int {
count := 0
for n > 0 {
count += n & 1
n >>= 1
}
return count
}