代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
当前回答
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;
}
其他回答
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++中循环移位(旋转)操作的最佳实践
对于232查找表和逐个遍历每个位之间的折中方法:
int bitcount(unsigned int num){
int count = 0;
static int nibblebits[] =
{0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
for(; num != 0; num >>= 4)
count += nibblebits[num & 0x0f];
return count;
}
从http://ctips.pbwiki.com/CountBits
下面是PHP中的一些东西(所有PHP整数都是32位符号,因此是31位):
function bits_population($nInteger)
{
$nPop=0;
while($nInteger)
{
$nInteger^=(1<<(floor(1+log($nInteger)/log(2))-1));
$nPop++;
}
return $nPop;
}
如果您恰好使用Java,则内置方法Integer。bitCount会这样做。
Java JDK1.5
Integer.bitCount (n);
其中n是要计算1的数。
检查,
Integer.highestOneBit(n);
Integer.lowestOneBit(n);
Integer.numberOfLeadingZeros(n);
Integer.numberOfTrailingZeros(n);
//Beginning with the value 1, rotate left 16 times
n = 1;
for (int i = 0; i < 16; i++) {
n = Integer.rotateLeft(n, 1);
System.out.println(n);
}