我总是在竞争性编程中使用它，它很容易写，而且效率很高:

#include <bits/stdc++.h>

using namespace std;

int countOnes(int n) {
    bitset<32> b(n);
    return b.count();
}

我在任何地方都没见过这种方法:

int nbits(unsigned char v) {
    return ((((v - ((v >> 1) & 0x55)) * 0x1010101) & 0x30c00c03) * 0x10040041) >> 0x1c;
}

它每字节工作一次，所以对于一个32位整数，它必须被调用四次。它源于横向加法，但它使用两个32位乘法将指令数量减少到只有7条。

大多数当前的C编译器将使用SIMD (SSE2)指令优化这个函数，当请求的数量是4的倍数时，它变得非常有竞争力。它是可移植的，可以定义为宏或内联函数，并且不需要数据表。

这种方法可以扩展为一次处理16位，使用64位乘法。但是，当所有16位都被设置时，它会失败，返回0，所以它只能在0xFFFF输入值不存在时使用。由于64位操作，它也比较慢，并且没有很好地优化。

如果你使用c++，另一个选择是使用模板元编程:

// recursive template to sum bits in an int
template <int BITS>
int countBits(int val) {
        // return the least significant bit plus the result of calling ourselves with
        // .. the shifted value
        return (val & 0x1) + countBits<BITS-1>(val >> 1);
}

// template specialisation to terminate the recursion when there's only one bit left
template<>
int countBits<1>(int val) {
        return val & 0x1;
}

用法如下:

// to count bits in a byte/char (this returns 8)
countBits<8>( 255 )

// another byte (this returns 7)
countBits<8>( 254 )

// counting bits in a word/short (this returns 1)
countBits<16>( 256 )

当然，你可以进一步扩展这个模板来使用不同的类型(甚至是自动检测位大小)，但为了清晰起见，我让它保持简单。

edit:忘了说这很好，因为它应该在任何c++编译器中工作，它基本上只是为你展开循环，如果一个常量值用于比特计数(换句话说，我很确定这是你能找到的最快的通用方法)

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;
}   

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

我认为最快的方法——不使用查找表和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位字。