代表数字7的8位像这样:

00000111

设置了三个比特。

确定32位整数中设置位数的算法是什么?


当前回答

另一个汉明权重算法,如果你使用的是BMI2 CPU:

the_weight = __tzcnt_u64(~_pext_u64(data[i], data[i]));

其他回答

我觉得很无聊,于是对三种方法进行了十亿次迭代。编译器是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,那么可以使用第二种方法。否则,请使用可读的(但速度较慢)一次一位的方法。

很难想象在什么情况下你会想要使用比特旋转方法。

编辑:这里也有类似的结果。

// How about the following:
public int CountBits(int value)
{
    int count = 0;
    while (value > 0)
    {
        if (value & 1)
            count++;
        value <<= 1;
    }
    return count;
}

从Python 3.10开始,你将能够使用int.bit_count()函数,但目前,你可以自己定义这个函数。

def bit_count(integer):
    return bin(integer).count("1")

以二进制表示计数集位(N):

伪代码,

设置counter = 0。 重复计数,直到N不为零。 检查最后一点。 如果最后一位= 1,则递增计数器 丢弃N的最后一位。

现在让我们用c++编写代码

int countSetBits(unsigned int n){

int count = 0;

while(n!=0){

    count += n&1;

    n = n >>1;
}

  return count;

}

我们用这个函数。

int main(){

 int x = 5;
 cout<<countSetBits(x);

 return 0;
}

输出:2

因为5有2位二进制表示(101)。

您可以在这里运行代码。

下面是PHP中的一些东西(所有PHP整数都是32位符号,因此是31位):

function bits_population($nInteger)
{

    $nPop=0;
    while($nInteger)
    {
        $nInteger^=(1<<(floor(1+log($nInteger)/log(2))-1));
        $nPop++;
    }
    return $nPop;
}