我认为最快的方法——不使用查找表和popcount——是以下方法。它仅通过12次操作来计数设置位。

int popcount(int v) {
    v = v - ((v >> 1) & 0x55555555);                // put count of each 2 bits into those 2 bits
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // put count of each 4 bits into those 4 bits  
    return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}

它之所以有效，是因为你可以通过将设置位分为两半来计算总设置位的数量，计算两半设置位的数量，然后将它们相加。也被称为分而治之范式。让我们来详细谈谈。

v = v - ((v >> 1) & 0x55555555); 

两位位数可以是0b00、0b01或0b10。让我们试着在2位上解决这个问题。

 ---------------------------------------------
 |   v    |   (v >> 1) & 0b0101   |  v - x   |
 ---------------------------------------------
   0b00           0b00               0b00   
   0b01           0b00               0b01     
   0b10           0b01               0b01
   0b11           0b01               0b10

这就是所需要的:最后一列显示每两个位对中设置位的计数。如果两个比特数>= 2 (0b10)，则产生0b01，否则产生0b00。

v = (v & 0x33333333) + ((v >> 2) & 0x33333333); 

这句话应该很容易理解。在第一个操作之后，我们每两个比特中就有一个set位的计数，现在我们每4个比特中就有一个set位的计数。

v & 0b00110011         //masks out even two bits
(v >> 2) & 0b00110011  // masks out odd two bits

然后我们把上面的结果加起来，得到4位的集合位总数。最后一个陈述是最棘手的。

c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;

让我们进一步分析一下……

v + (v >> 4)

这和第二种说法很相似;我们以4为一组来计数集合位。因为我们之前的运算，我们知道每一个咬痕都有一个集合位的计数。让我们看一个例子。假设我们有字节0b01000010。这意味着第一个啃食有它的4位设置，第二个有它的2位设置。现在我们把这些小块加在一起。

v = 0b01000010
(v >> 4) = 0b00000100
v + (v >> 4) = 0b01000010 + 0b00000100

它为我们提供了一个字节中set位的计数，在第二个nibble 0b01000110中，因此我们掩码了该数字中所有字节的前四个字节(丢弃它们)。

0b01000110 & 0x0F = 0b00000110

现在每个字节都有一个集合位的计数。我们需要把它们全部加起来。诀窍是将结果乘以0b10101010，它有一个有趣的属性。如果我们的数字有四个字节，A B C D，它将产生一个新的数字，包含这些字节A+B+C+D B+C+D C+D。一个4字节的数字最多可以设置32位，可以表示为0b00100000。

我们现在需要的是第一个字节，它是所有字节中所有set位的和，我们通过>> 24得到它。该算法是为32位字设计的，但可以很容易地修改为64位字。

一个简单的算法来计算设置位的数量:

int countbits(n) {
    int count = 0;
    while(n != 0) {
        n = n & (n-1);
        count++;
    }
    return count;
}

以11(1011)为例，尝试手动运行该算法。它应该对你有很大帮助!

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++中循环移位(旋转)操作的最佳实践

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，并保持所有其他位相同。

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

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

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

function bits_population($nInteger)
{

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