代表数字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);
}
}
其他回答
我觉得很无聊,于是对三种方法进行了十亿次迭代。编译器是gcc -O3。CPU就是第一代Macbook Pro里装的东西。
最快的是3.7秒:
static unsigned char wordbits[65536] = { bitcounts of ints between 0 and 65535 };
static int popcount( unsigned int i )
{
return( wordbits[i&0xFFFF] + wordbits[i>>16] );
}
第二名是相同的代码,但查找的是4个字节而不是2个半字。这花了大约5.5秒。
第三名是“横向加法”法,用时8.6秒。
第四名是GCC的__builtin_popcount(),仅为11秒。
一次一个比特的计数方法要慢得多,我厌倦了等待它完成。
因此,如果您最关心的是性能,那么请使用第一种方法。如果您关心它,但又不想在上面花费64Kb的RAM,那么可以使用第二种方法。否则,请使用可读的(但速度较慢)一次一位的方法。
很难想象在什么情况下你会想要使用比特旋转方法。
编辑:这里也有类似的结果。
这可以在O(k)中完成,其中k是设置的比特数。
int NumberOfSetBits(int n)
{
int count = 0;
while (n){
++ count;
n = (n - 1) & n;
}
return count;
}
c++ 20 std:: popcount
以下建议已合并http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p0553r4.html,并应将其添加到<bit>头。
我希望用法是这样的:
#include <bit>
#include <iostream>
int main() {
std::cout << std::popcount(0x55) << std::endl;
}
当支持GCC时,我会尝试一下,GCC 9.1.0带有g++-9 -std=c++2a仍然不支持它。
提案说:
标题:< > 命名空间STD { // 25.5.6,计数 模板类T > < conexpr int popcount(T x) noexcept;
and:
模板类T > < conexpr int popcount(T x) noexcept; 约束:T是无符号整数类型(3.9.1 [basic.fundamental])。 返回:x值中的1位数。
std::rotl和std::rotr也被添加来执行循环位旋转:c++中循环移位(旋转)操作的最佳实践
#!/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
Python的解决方案:
def hammingWeight(n: int) -> int:
sums = 0
while (n!=0):
sums+=1
n = n &(n-1)
return sums
在二进制表示中,n中最不有效的1位总是对应n - 1中的0位。因此,对n和n - 1这两个数进行and运算总是将n中最不有效的1位翻转为0,并保持所有其他位相同。