你要找的函数通常被称为二进制数的“横向和”或“总体数”。Knuth在前分册1A，第11-12页中讨论了它(尽管在第2卷，4.6.3-(7)中有简要的参考)。

经典文献是Peter Wegner的文章“二进制计算机中的一种计数技术”，摘自ACM通讯，卷3(1960)第5号，第322页。他给出了两种不同的算法，一种针对“稀疏”(即1的数量很少)的数字进行了优化，另一种针对相反的情况。

为什么不迭代地除以2呢?

count = 0
while n > 0
  if (n % 2) == 1
    count += 1
  n /= 2  

我同意这不是最快的，但是“最好”这个词有点含糊不清。我认为“最好”应该有一个清晰的元素

有些语言以一种可以使用有效硬件支持(如果可用的话)的方式可移植地公开操作，而有些语言则希望使用一些不错的库。

例如(从语言表中):

c++有std::bitset<>::count()或c++ 20 std::popcount(T x) Java有Java .lang. integer . bitcount()(也用于Long或BigInteger) c#有system . numbers . bitoperations . popcount () Python有int.bit_count()(从3.10开始)

不过，并不是所有的编译器/库都能在HW支持可用时使用它。(值得注意的是MSVC，即使有选项使std::popcount内联为x86 popcnt，它的std::bitset::count仍然总是使用查找表。这有望在未来的版本中改变。)

当可移植语言没有这种基本的位操作时，还要考虑编译器的内置函数。以GNU C为例:

int __builtin_popcount (unsigned int x);
int __builtin_popcountll (unsigned long long x);

In the worst case (no single-instruction HW support) the compiler will generate a call to a function (which in current GCC uses a shift/and bit-hack like this answer, at least for x86). In the best case the compiler will emit a cpu instruction to do the job. (Just like a * or / operator - GCC will use a hardware multiply or divide instruction if available, otherwise will call a libgcc helper function.) Or even better, if the operand is a compile-time constant after inlining, it can do constant-propagation to get a compile-time-constant popcount result.

GCC内置甚至可以跨多个平台工作。Popcount几乎已经成为x86架构的主流，所以现在开始使用内置是有意义的，这样你就可以重新编译，让它内联硬件指令时，你编译-mpopcnt或包括(例如https://godbolt.org/z/Ma5e5a)。其他架构已经有popcount很多年了，但在x86领域，仍然有一些古老的Core 2和类似的老式AMD cpu在使用。

---

在x86上，你可以告诉编译器它可以通过-mpopcnt(也可以通过-msse4.2暗示)假设支持popcnt指令。参见GCC x86选项。-march=nehalem -mtune=skylake(或-march=任何您希望您的代码假设和调优的CPU)可能是一个不错的选择。在较旧的CPU上运行生成的二进制文件将导致非法指令错误。

要为构建它们的机器优化二进制文件，请使用-march=native(与gcc、clang或ICC一起使用)。

MSVC为x86的popcnt指令提供了一个内在的特性，但与gcc不同的是，它实际上是硬件指令的一个内在特性，需要硬件支持。

---

使用std::bitset<>::count()代替内置的

理论上，任何知道如何有效地为目标CPU进行popcount的编译器都应该通过ISO c++ std::bitset<>来公开该功能。实际上，对于某些目标cpu，在某些情况下使用bit-hack AND/shift/ADD可能会更好。

For target architectures where hardware popcount is an optional extension (like x86), not all compilers have a std::bitset that takes advantage of it when available. For example, MSVC has no way to enable popcnt support at compile time, and it's std::bitset<>::count always uses a table lookup, even with /Ox /arch:AVX (which implies SSE4.2, which in turn implies the popcnt feature.) (Update: see below; that does get MSVC's C++20 std::popcount to use x86 popcnt, but still not its bitset<>::count. MSVC could fix that by updating their standard library headers to use std::popcount when available.)

但是，至少您得到了可以在任何地方工作的可移植的东西，并且使用带有正确目标选项的gcc/clang，您可以获得支持它的体系结构的硬件popcount。

#include <bitset>
#include <limits>
#include <type_traits>

template<typename T>
//static inline  // static if you want to compile with -mpopcnt in one compilation unit but not others
typename std::enable_if<std::is_integral<T>::value,  unsigned >::type 
popcount(T x)
{
    static_assert(std::numeric_limits<T>::radix == 2, "non-binary type");

    // sizeof(x)*CHAR_BIT
    constexpr int bitwidth = std::numeric_limits<T>::digits + std::numeric_limits<T>::is_signed;
    // std::bitset constructor was only unsigned long before C++11.  Beware if porting to C++03
    static_assert(bitwidth <= std::numeric_limits<unsigned long long>::digits, "arg too wide for std::bitset() constructor");

    typedef typename std::make_unsigned<T>::type UT;        // probably not needed, bitset width chops after sign-extension

    std::bitset<bitwidth> bs( static_cast<UT>(x) );
    return bs.count();
}

参见Godbolt编译器资源管理器上gcc、clang、icc和MSVC中的asm。

x86-64 gcc -O3 -std=gnu++11 -mpopcnt输出:

unsigned test_short(short a) { return popcount(a); }
    movzx   eax, di      # note zero-extension, not sign-extension
    popcnt  rax, rax
    ret

unsigned test_int(int a) { return popcount(a); }
    mov     eax, edi
    popcnt  rax, rax        # unnecessary 64-bit operand size
    ret

unsigned test_u64(unsigned long long a) { return popcount(a); }
    xor     eax, eax     # gcc avoids false dependencies for Intel CPUs
    popcnt  rax, rdi
    ret

PowerPC64 gcc -O3 -std=gnu++11发出(对于int arg版本):

    rldicl 3,3,0,32     # zero-extend from 32 to 64-bit
    popcntd 3,3         # popcount
    blr

这个源代码不是x86特定的，也不是gnu特定的，只是在gcc/clang/icc下编译得很好，至少在针对x86(包括x86-64)时是这样。

还要注意，对于没有单指令popcount的体系结构，gcc的回退是逐字节表查找。例如，这对ARM来说就不是什么好事。

c++ 20有std::popcount(T)

不幸的是，当前libstdc++头文件用特殊情况定义了它，if(x==0) return 0;在开始时，clang在编译x86时不会优化:

#include <bit>
int bar(unsigned x) {
    return std::popcount(x);
}

clang 11.0.1 -O3 -std=gnu++20 -march=nehalem （https://godbolt.org/z/arMe5a）

# clang 11
    bar(unsigned int):                                # @bar(unsigned int)
        popcnt  eax, edi
        cmove   eax, edi         # redundant: if popcnt result is 0, return the original 0 instead of the popcnt-generated 0...
        ret

但是GCC编译得很好:

# gcc 10
        xor     eax, eax         # break false dependency on Intel SnB-family before Ice Lake.
        popcnt  eax, edi
        ret

即使是MSVC也能很好地使用它，只要你使用-arch:AVX或更高版本(并使用-std:c++latest启用c++ 20)。https://godbolt.org/z/7K4Gef

int bar(unsigned int) PROC                                 ; bar, COMDAT
        popcnt  eax, ecx
        ret     0
int bar(unsigned int) ENDP                                 ; bar

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

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

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

对于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

我特别喜欢这个来自《财富》的例子:

#define BITCOUNT(x)    (((BX_(x)+(BX_(x)>>4)) & 0x0F0F0F0F) % 255)
#define BX_(x)         ((x) - (((x)>>1)&0x77777777)
                             - (((x)>>2)&0x33333333)
                             - (((x)>>3)&0x11111111))

我最喜欢它，因为它太漂亮了!