以二进制表示计数集位(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)。

您可以在这里运行代码。

摘自《黑客的喜悦》第66页，图5-2

int pop(unsigned x)
{
    x = x - ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F;
    x = x + (x >> 8);
    x = x + (x >> 16);
    return x & 0x0000003F;
}

执行大约20条指令(依赖于arch)，没有分支。黑客的喜悦是令人愉快的!强烈推荐。

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

function bits_population($nInteger)
{

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

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

例如(从语言表中):

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

当你写出比特模式时，“黑客的喜悦”比特旋转变得更加清晰。

unsigned int bitCount(unsigned int x)
{
  x = ((x >> 1) & 0b01010101010101010101010101010101)
     + (x       & 0b01010101010101010101010101010101);
  x = ((x >> 2) & 0b00110011001100110011001100110011)
     + (x       & 0b00110011001100110011001100110011); 
  x = ((x >> 4) & 0b00001111000011110000111100001111)
     + (x       & 0b00001111000011110000111100001111); 
  x = ((x >> 8) & 0b00000000111111110000000011111111)
     + (x       & 0b00000000111111110000000011111111); 
  x = ((x >> 16)& 0b00000000000000001111111111111111)
     + (x       & 0b00000000000000001111111111111111); 
  return x;
}

第一步将偶数位加到奇数位上，产生每两个位的和。其他步骤将高阶数据块添加到低阶数据块，将数据块的大小一直增加一倍，直到最终计数占用整个int。

#!/user/local/bin/perl


    $c=0x11BBBBAB;
     $count=0;
     $m=0x00000001;
    for($i=0;$i<32;$i++)
    {
        $f=$c & $m;
        if($f == 1)
        {
            $count++;
        }
        $c=$c >> 1;
    }
    printf("%d",$count);

ive done it through a perl script. the number taken is $c=0x11BBBBAB   
B=3 1s   
A=2 1s   
so in total  
1+1+3+3+3+2+3+3=19