计算32位整数中的设置位数

这被称为“汉明体重”，“popcount”或“横向加法”。

一些CPU有一个内置指令来执行它，而另一些CPU有并行指令来作用于位向量。像x86的popcnt（在支持它的CPU上）这样的指令几乎肯定是单个整数最快的。其他一些架构可能有一个缓慢的指令，用一个微编码循环来实现，每个周期测试一个位（需要引用-硬件流行计数通常很快，如果它存在的话）。

“最佳”算法实际上取决于您使用的CPU以及您的使用模式。

编译器可能知道如何做一些对你要编译的特定CPU有益的事情，例如C++20#0或C++std::bitset<32>::count()，作为访问内置/内在函数的可移植方法（请参阅这个问题的另一个答案）。但是编译器为没有硬件popcnt的目标CPU选择的回退可能不适合你的用例。或者你的语言（例如C）可能不会公开任何可以使用CPU特定流行计数的可移植函数，当有时。

不需要（或受益于）任何硬件支持的便携式算法

如果您的CPU具有较大的缓存并且您在紧密循环中执行大量此类操作，则预填充的表查找方法可以非常快。然而，由于“缓存未命中”的代价，CPU必须从主存储器中获取一些表，它可能会受到影响。（分别查找每个字节以保持表小。）如果您想要连续数字范围的popcoun，则只有低字节在256个数字的组中发生变化，使这个非常好。

如果您知道您的字节将主要是0或主要是1，那么对于这些场景有有效的算法，例如在循环中使用bithack清除最低集，直到它变成零。

我相信一个非常好的通用算法如下，称为“并行”或“可变精度SWAR算法”。我用类似C的伪语言表达了这一点，你可能需要调整它以适用于特定语言（例如，在Java中使用uint32_tC++和>>>）：

GCC10和clang 10.0可以识别这种模式/习惯用法，并在可用时将其编译为硬件popcnt或等效指令，为您提供两全其美的效果。（https://godbolt.org/z/qGdh1dvKK）

int numberOfSetBits(uint32_t i){// Java: use int, and use >>> instead of >>. Or use Integer.bitCount()// C or C++: use uint32_ti = i - ((i >> 1) & 0x55555555);        // add pairs of bitsi = (i & 0x33333333) + ((i >> 2) & 0x33333333);  // quadsi = (i + (i >> 4)) & 0x0F0F0F0F;        // groups of 8return (i * 0x01010101) >> 24;          // horizontal sum of bytes}

对于JavaScript：强制为整数和|0的性能：将第一行更改为i = (i|0) - ((i >> 1) & 0x55555555);

这在所讨论的任何算法中具有最佳的最坏情况行为，因此可以有效地处理您抛出的任何使用模式或值。（它的性能不依赖于普通CPU的数据，其中包括乘法在内的所有整数运算都是常数时间。通过“简单”输入，它不会变得更快，但它仍然相当不错。）

参考文献：

• https://graphics.stanford.edu/~seander/bithacks.html
• https://catonmat.net/low-level-bit-hacks用于bithack基础知识，例如减去1如何翻转连续的零。
• https://en.wikipedia.org/wiki/Hamming_weight
• http://gurmeet.net/puzzles/fast-bit-counting-routines/
• http://aggregate.ee.engr.uky.edu/MAGIC/#Population%20Count%20（1%20Count）

这个SWAR bithack是如何工作的：

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

第一步是掩码的优化版本，以隔离奇数/偶数位，移动以使它们对齐，然后相加。这有效地在2位累加器中进行了16次单独的添加（SWAR=寄存器内的SIMD）。像(i & 0x55555555) + ((i>>1) & 0x55555555)一样。

下一步将这些16x 2位累加器中的奇数/偶数8个累加器再次相加，产生8x 4位总和。这次不可能进行i - ...优化，因此它只会在移位之前/之后进行屏蔽。在编译需要单独在寄存器中构造32位常量的ISA时，两次使用相同的0x33...常量而不是0xccc...移位之前是一件好事。

(i + (i >> 4)) & 0x0F0F0F0F的最后移位加法步骤扩大到4x 8位累加器。它掩盖了之后而不是之前的加法，因为如果设置了相应输入位的所有4位，任何4位累加器的最大值都是4。4+4=8仍然适合4位，因此在i + (i >> 4)中，半字节元素之间的进位是不可能的。

到目前为止，这只是使用SWAR技术进行一些巧妙优化的相当正常的SIMD。继续使用相同的模式再进行2个步骤可以扩大到2x 16位然后1x 32位计数。但是在具有快速硬件乘法的机器上有一种更有效的方法：

一旦我们有足够少的“元素”，一个带有魔法常数的乘法可以将所有元素求和到顶部元素。在这种情况下是字节元素。乘法是通过左移和加法完成的，所以#0的乘法结果是#1。我们的8位元素足够宽（并且保持足够小的计数），这不会产生前8位的进位成。

这个的64位版本可以使用0x01010101010101乘法器在64位整数中执行8 x 8位元素，并使用>>56提取高字节。因此它不需要任何额外的步骤，只需更宽的常量。这就是GCC在x86系统上未启用硬件popcnt指令时用于__builtin_popcountll的内容。如果您可以为此使用内置或内在函数，请这样做以使编译器有机会进行特定于目标的优化。

对于更宽的向量（例如计数整个数组）具有完整的SIMD

这种按位SWAR算法可以一次在多个向量元素中并行执行，而不是在单个整数寄存器中，以便在具有SIMD但没有可用popcount指令的CPU上进行加速（例如，必须在任何CPU上运行的x86-64代码，而不仅仅是Nehalem或更高版本）。

然而，将向量指令用于popcount的最佳方法通常是使用变量洗牌在并行的每个字节的时间对4位进行表查找。（4位索引向量寄存器中保存的16个条目表）。

在英特尔CPU上，硬件64位popcnt指令的性能可以超过SSSE3#0位并行实现大约2倍，但只有如果您的编译器得到它恰到好处。否则SSE可以明显领先。较新的编译器版本知道popcnt错误依赖英特尔上的问题。

• https://github.com/WojciechMula/sse-popcount用于SSSE3、AVX2、AVX512BW、AVX512VBMI或AVX512 VPOPCNT的最先进的x86 SIMD流行计数。跨向量使用Harley-Seal来推迟元素内的流行计数。（也是ARM NEON）
• 使用AVX-512或AVX-2在大数据上计数1位（总体计数）
• 相关：https://github.com/mklarqvist/positional-popcount-多个8、16、32或64位整数的每个位位置的单独计数。（同样，x86 SIMD包括AVX-512，它非常擅长此，vpternlogd使Harley-Seal非常很好。）

为什么不迭代除以2？

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

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

如果您碰巧使用Java，内置方法Integer.bitCount将执行此操作。

一些语言以可以使用有效硬件支持（如果可用）的方式可移植地公开操作，否则一些希望体面的库回退。

例如（从按语言排列的表格开始）：

• C++有std::bitset<>::count()或C++20#1
• Java有java.lang.Integer.bitCount()（也用于Long或BigInteger）
• C#有System.Numerics.BitOperations.PopCount()
• Python有int.bit_count()（从3.10开始）

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

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

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

在最坏的情况下（没有单指令硬件支持），编译器将生成对一个函数的调用（在当前的GCC中，它使用了Shift/和bit-hack喜欢这个答案，至少对于x86）。在最好的情况下，编译器将发出一条cpu指令来完成这项工作。（就像*或/操作符一样——如果可用，GCC将使用硬件乘法或除法指令，否则将调用libgcc辅助函数。）或者更好的是，如果操作数是内联后的编译时常量，它可以进行常量传播以获得编译时常量popcoun结果。

GCC内置程序甚至可以跨多个平台工作。PopCount几乎已经成为x86架构的主流，所以现在开始使用内置程序是有意义的，这样当你用-mpopcnt或包含它的东西（例如https://godbolt.org/z/Ma5e5a）编译时，你就可以重新编译，让它内联硬件指令。其他架构已经使用popCount多年了，但在x86世界中仍然有一些古老的Core 2和类似的老式AMD CPU在使用中。

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

为了使二进制文件针对您构建它们的机器进行优化，使用#0（使用gcc、clang或ICC）。

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

使用std::bitset<>::count()而不是内置

从理论上讲，任何知道如何有效地为目标CPU进行弹出计数的编译器都应该通过ISOC++std::bitset<>公开该功能。在实践中，在某些情况下，对于某些目标CPU，您可能最好使用位破解AND/Shift/ADD。

对于硬件popcount是可选扩展（如x86）的目标体系结构，并非所有编译器都有一个std::bitset在可用时利用它。例如，MSVC无法在编译时启用popcnt支持，它的std::bitset<>::count总是使用一个表查找，即使有/Ox /arch:AVX（这意味着SSE4.2，这反过来又意味着popcnt功能。）（更新：见下文；确实让MSVC的C++20std::popcount使用x86popcnt，但仍然不是它的bitset<>::count。MSVC可以通过更新他们的标准库标头来使用std::popcount来解决这个问题。）

但至少你得到了可以在任何地方工作的可移植的东西，并且使用具有正确目标选项的gcc/clang，你可以获得支持它的架构的硬件流行计数。

#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 otherstypename std::enable_if<std::is_integral<T>::value,  unsigned >::typepopcount(T x){static_assert(std::numeric_limits<T>::radix == 2, "non-binary type");
// sizeof(x)*CHAR_BITconstexpr 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++03static_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();}

参见asm从gcc，clang，icc，和MSVC在戈波特编译器资源管理器。

x86-64gcc -O3 -std=gnu++11 -mpopcnt发出：

unsigned test_short(short a) { return popcount(a); }movzx   eax, di      # note zero-extension, not sign-extensionpopcnt  rax, raxret
unsigned test_int(int a) { return popcount(a); }mov     eax, edipopcnt  rax, rax        # unnecessary 64-bit operand sizeret
unsigned test_u64(unsigned long long a) { return popcount(a); }xor     eax, eax     # gcc avoids false dependencies for Intel CPUspopcnt  rax, rdiret

PowerPC64gcc -O3 -std=gnu++11发出（对于int arg版本）：

    rldicl 3,3,0,32     # zero-extend from 32 to 64-bitpopcntd 3,3         # popcountblr

这个源代码根本不是x86特定的或GNU特定的，但只能与gcc/clang/icc很好地编译，至少在针对x86（包括x86-64）时是这样。

另请注意，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 11bar(unsigned int):                                # @bar(unsigned int)popcnt  eax, edicmove   eax, edi         # redundant: if popcnt result is 0, return the original 0 instead of the popcnt-generated 0...ret

但是GCC编译得很好：

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

即使MSVC也能很好地使用它，只要您使用-arch:AVX或更高版本（并使用-std:c++latest启用C++20）。

int bar(unsigned int) PROC                                 ; bar, COMDATpopcnt  eax, ecxret     0int bar(unsigned int) ENDP                                 ; bar

你说的“最佳算法”是什么意思？短代码还是快代码？你的代码看起来很优雅，并且执行时间不变。代码也很短。

但是，如果速度是主要因素而不是代码大小，那么我认为以下内容可以更快：

       static final int[] BIT_COUNT = { 0, 1, 1, ... 256 values with a bitsize of a byte ... };static int bitCountOfByte( int value ){return BIT_COUNT[ value & 0xFF ];}
static int bitCountOfInt( int value ){return bitCountOfByte( value )+ bitCountOfByte( value >> 8 )+ bitCountOfByte( value >> 16 )+ bitCountOfByte( value >> 24 );}

我认为这对于64位值不会更快，但32位值可以更快。

来自Hacker's Delight，第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-ish指令中执行（依赖于架构），没有分支。

黑客的喜悦是令人愉快！强烈推荐。

在我看来，“最好”的解决方案是一个可以被另一个程序员（或两年后的原始程序员）阅读而没有大量评论的解决方案。你很可能想要一些已经提供的最快或最聪明的解决方案，但我更喜欢易读性而不是聪明。

unsigned int bitCount (unsigned int value) {unsigned int count = 0;while (value > 0) {           // until all bits are zeroif ((value & 1) == 1)     // check lower bitcount++;value >>= 1;              // shift bits, removing lower bit}return count;}

如果您想要更快的速度（并且假设您很好地记录了它以帮助您的继任者），您可以使用表查找：

// Lookup table for fast calculation of bits set in 8-bit unsigned char.
static unsigned char oneBitsInUChar[] = {//  0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F (<- n)//  =====================================================0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, // 0n1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, // 1n: : :4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, // Fn};
// Function for fast calculation of bits set in 16-bit unsigned short.
unsigned char oneBitsInUShort (unsigned short x) {return oneBitsInUChar [x >>    8]+ oneBitsInUChar [x &  0xff];}
// Function for fast calculation of bits set in 32-bit unsigned int.
unsigned char oneBitsInUInt (unsigned int x) {return oneBitsInUShort (x >>     16)+ oneBitsInUShort (x &  0xffff);}

这些依赖于特定的数据类型大小，因此它们不是那么可移植的。但是，由于许多性能优化无论如何都不可移植，这可能不是问题。如果你想要可移植性，我会坚持使用可读的解决方案。

对于2³²查找表和单独迭代每个位之间的快乐媒介：

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))

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

您要查找的函数通常称为二进制数的“横向求和”或“总体计数”。Knuth在预分册1A中讨论了它，pp11-12（尽管在第2卷4.6.3-（7）中有简短的参考）。

经典位点是Peter Wegner的文章“在二进制计算机中计数的技术”，来自ACM通讯，第3卷（1960年）第5号，第322页。他在那里给出了两种不同的算法，一种针对预期“稀疏”的数字（即有少量的数字）进行了优化，另一种针对相反的情况。

我感到无聊，并为三种方法的十亿次迭代计时。编译器是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秒。

第四名是海湾合作委员会的__builtin_popcount（），可耻的11秒。

一次计算一位的方法慢了一点，我厌倦了等待它完成。

因此，如果您关心性能高于一切，请使用第一种方法。如果您关心，但不足以在其上花费64Kb的RAM，请使用第二种方法。否则请使用可读（但缓慢）的一次一位方法。

很难想象在什么情况下你会想使用微调方法。

编辑：类似的结果这里。

这是那些有助于了解微架构的问题之一。我刚刚在gcc 4.3.3下使用-O3编译了两个变体，使用C++内联来消除函数调用开销，十亿次迭代，保持所有计数的运行和以确保编译器不会删除任何重要的东西，使用rdtsc进行计时（时钟周期精确）。

inline int pop2(unsigned x, unsigned y){x = x - ((x >> 1) & 0x55555555);y = y - ((y >> 1) & 0x55555555);x = (x & 0x33333333) + ((x >> 2) & 0x33333333);y = (y & 0x33333333) + ((y >> 2) & 0x33333333);x = (x + (x >> 4)) & 0x0F0F0F0F;y = (y + (y >> 4)) & 0x0F0F0F0F;x = x + (x >> 8);y = y + (y >> 8);x = x + (x >> 16);y = y + (y >> 16);return (x+y) & 0x000000FF;}

未经修改的Hacker's Delight需要12.2千兆循环。我的并行版本（位数是其两倍）运行13.0千兆循环。在2.4GHz Core Duo上，两者总共花费了10.5秒。25千兆循环=在这个时钟频率下刚刚超过10秒，所以我相信我的时间是正确的。

这与指令依赖链有关，这对该算法非常不利。通过使用一对64位寄存器，我几乎可以将速度提高一倍。事实上，如果我聪明一点，早一点添加x+y，我可以减少一些变化。64位版本经过一些小调整后，会产生大约偶数，但会再次计算两倍的位。

使用128位SIMD寄存器，这是另一个因素，SSE指令集通常也有巧妙的捷径。

代码没有理由特别透明。接口简单，算法可以在很多地方在线引用，并且适合进行全面的单元测试。偶然发现它的程序员甚至可能会学到一些东西。这些位操作在机器级别是极其自然的。

好的，我决定使用调整后的64位版本。对于这个sizeof（无符号长）==8

inline int pop2(unsigned long x, unsigned long y){x = x - ((x >> 1) & 0x5555555555555555);y = y - ((y >> 1) & 0x5555555555555555);x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);y = (y & 0x3333333333333333) + ((y >> 2) & 0x3333333333333333);x = (x + (x >> 4)) & 0x0F0F0F0F0F0F0F0F;y = (y + (y >> 4)) & 0x0F0F0F0F0F0F0F0F;x = x + y;x = x + (x >> 8);x = x + (x >> 16);x = x + (x >> 32);return x & 0xFF;}

看起来差不多（不过我没有仔细测试）。现在的计时结果是10.70千兆/14.1千兆。后来的数字加起来1280亿位，对应于这台机器上经过的5.9秒。非并行版本加快了一点，因为我在64位模式下运行，它喜欢64位寄存器比32位寄存器稍微好一点。

让我们看看这里是否有更多的OOO流水线。这有点复杂，所以我实际上测试了一下。每个项单独总和为64，所有总和为256。

inline int pop4(unsigned long x, unsigned long y,unsigned long u, unsigned long v){enum { m1 = 0x5555555555555555,m2 = 0x3333333333333333,m3 = 0x0F0F0F0F0F0F0F0F,m4 = 0x000000FF000000FF };
x = x - ((x >> 1) & m1);y = y - ((y >> 1) & m1);u = u - ((u >> 1) & m1);v = v - ((v >> 1) & m1);x = (x & m2) + ((x >> 2) & m2);y = (y & m2) + ((y >> 2) & m2);u = (u & m2) + ((u >> 2) & m2);v = (v & m2) + ((v >> 2) & m2);x = x + y;u = u + v;x = (x & m3) + ((x >> 4) & m3);u = (u & m3) + ((u >> 4) & m3);x = x + u;x = x + (x >> 8);x = x + (x >> 16);x = x & m4;x = x + (x >> 32);return x & 0x000001FF;}

有一阵子我很兴奋，但事实证明，尽管我在一些测试中没有使用inline关键字，但gcc正在用-O3玩内联技巧。当我让gcc玩技巧时，对pop4（）的十亿次调用需要12.56千兆循环，但我确定这是将参数折叠为常量表达式。更现实的数字似乎是19.6gc，再加速30%。我的测试循环现在看起来像这样，确保每个参数的不同足以阻止gcc玩技巧。

hitime b4 = rdtsc();for (unsigned long i = 10L * 1000*1000*1000; i < 11L * 1000*1000*1000; ++i)sum += pop4 (i,  i^1, ~i, i|1);hitime e4 = rdtsc();

经过8.17秒的2560亿位求和。在16位表查找中作为基准测试的3200万位计算为1.02秒。无法直接比较，因为另一个工作台没有给出时钟速度，但看起来我已经将64KB表版本的鼻涕赶走了，这首先是L1缓存的悲惨使用。

更新：决定做一个显而易见的事情，通过添加四条重复的行来创建pop6（）。结果是22.8gc，3840亿位在9.5s中相加。所以还有另外20%Now在800毫秒用于320亿位。

几个悬而未决的问题：-

1. 如果数字是负数，？
2. 如果数字是1024，那么“迭代除以2”方法将迭代10次。

我们可以修改算法来支持负数如下：-

count = 0while n != 0if ((n % 2) == 1 || (n % 2) == -1count += 1n /= 2return count

现在，为了克服第二个问题，我们可以编写如下算法：

int bit_count(int num){int count=0;while(num){num=(num)&(num-1);count++;}return count;}

完整参考见：

http://goursaha.freeoda.com/Miscellaneous/IntegerBitCount.html

一个简单的方法应该可以很好地为少量的比特工作，就像这样（对于这个例子中的4位）：

（i&1）+（i&2）/2+（i&4）/4+（i&8）/8

其他人会推荐这对于少量位作为一个简单的解决方案吗？

我在大约1990年为RISC机器编写了一个快速位计数宏。它不使用高级算术（乘法、除法、%）、内存获取（太慢了）、分支（太慢了），但它确实假设CPU有一个32位的桶移位器（换句话说，>>1和>>32占用相同的周期。）它假设小常量（如6、12、24）不需要任何成本即可加载到寄存器中，或者存储在临时文件中并一遍又一遍地重用。

在这些假设下，它在大多数RISC机器上大约16个周期/指令中计数32位。请注意，15条指令/周期接近循环或指令数量的下界，因为似乎至少需要3条指令（掩码、移位、运算符）才能将加数数量减半，所以log_2（32）=5,5 x 3=15条指令是准下界。

#define BitCount(X,Y)           \Y = X - ((X >> 1) & 033333333333) - ((X >> 2) & 011111111111); \Y = ((Y + (Y >> 3)) & 030707070707); \Y =  (Y + (Y >> 6)); \Y = (Y + (Y >> 12) + (Y >> 24)) & 077;

以下是第一个也是最复杂的步骤的秘密：

input outputAB    CD             Note00    00             = AB01    01             = AB10    01             = AB - (A >> 1) & 0x111    10             = AB - (A >> 1) & 0x1

所以如果我取上面的第一列（A），向右移动1位，然后从AB中减去它，我得到输出（CD）。扩展到3位是相似的；如果你愿意，你可以用一个8行的布尔表检查它，就像上面的我一样。

• 唐·吉利斯

JavaJDK1.5

Integer.bit计数（n）；

其中n是其1要被计数的数。

也检查，

Integer.highestOneBit(n);Integer.lowestOneBit(n);Integer.numberOfLeadingZeros(n);Integer.numberOfTrailingZeros(n);
//Beginning with the value 1, rotate left 16 timesn = 1;for (int i = 0; i < 16; i++) {n = Integer.rotateLeft(n, 1);System.out.println(n);}

这是一个可移植模块（ANSI-C），它可以在任何架构上对您的每个算法进行基准测试。

你的CPU有9位字节？没问题：-）目前它实现了2种算法，K&R算法和按字节查找表。查找表平均比K&R算法快3倍。如果有人能想出一种方法来使“Hacker's Delight”算法可移植，请随时添加它。

#ifndef _BITCOUNT_H_#define _BITCOUNT_H_
/* Return the Hamming Wieght of val, i.e. the number of 'on' bits. */int bitcount( unsigned int );
/* List of available bitcount algorithms.* onTheFly:    Calculate the bitcount on demand.** lookupTalbe: Uses a small lookup table to determine the bitcount.  This* method is on average 3 times as fast as onTheFly, but incurs a small* upfront cost to initialize the lookup table on the first call.** strategyCount is just a placeholder.*/enum strategy { onTheFly, lookupTable, strategyCount };
/* String represenations of the algorithm names */extern const char *strategyNames[];
/* Choose which bitcount algorithm to use. */void setStrategy( enum strategy );
#endif

.

#include <limits.h>
#include "bitcount.h"
/* The number of entries needed in the table is equal to the number of unique* values a char can represent which is always UCHAR_MAX + 1*/static unsigned char _bitCountTable[UCHAR_MAX + 1];static unsigned int _lookupTableInitialized = 0;
static int _defaultBitCount( unsigned int val ) {int count;
/* Starting with:* 1100 - 1 == 1011,  1100 & 1011 == 1000* 1000 - 1 == 0111,  1000 & 0111 == 0000*/for ( count = 0; val; ++count )val &= val - 1;
return count;}
/* Looks up each byte of the integer in a lookup table.** The first time the function is called it initializes the lookup table.*/static int _tableBitCount( unsigned int val ) {int bCount = 0;
if ( !_lookupTableInitialized ) {unsigned int i;for ( i = 0; i != UCHAR_MAX + 1; ++i )_bitCountTable[i] =( unsigned char )_defaultBitCount( i );
_lookupTableInitialized = 1;}
for ( ; val; val >>= CHAR_BIT )bCount += _bitCountTable[val & UCHAR_MAX];
return bCount;}
static int ( *_bitcount ) ( unsigned int ) = _defaultBitCount;
const char *strategyNames[] = { "onTheFly", "lookupTable" };
void setStrategy( enum strategy s ) {switch ( s ) {case onTheFly:_bitcount = _defaultBitCount;break;case lookupTable:_bitcount = _tableBitCount;break;case strategyCount:break;}}
/* Just a forwarding function which will call whichever version of the* algorithm has been selected by the client*/int bitcount( unsigned int val ) {return _bitcount( val );}
#ifdef _BITCOUNT_EXE_
#include <stdio.h>#include <stdlib.h>#include <time.h>
/* Use the same sequence of pseudo random numbers to benmark each Hamming* Weight algorithm.*/void benchmark( int reps ) {clock_t start, stop;int i, j;static const int iterations = 1000000;
for ( j = 0; j != strategyCount; ++j ) {setStrategy( j );
srand( 257 );
start = clock(  );
for ( i = 0; i != reps * iterations; ++i )bitcount( rand(  ) );
stop = clock(  );
printf( "\n\t%d psudoe-random integers using %s: %f seconds\n\n",reps * iterations, strategyNames[j],( double )( stop - start ) / CLOCKS_PER_SEC );}}
int main( void ) {int option;
while ( 1 ) {printf( "Menu Options\n""\t1.\tPrint the Hamming Weight of an Integer\n""\t2.\tBenchmark Hamming Weight implementations\n""\t3.\tExit ( or cntl-d )\n\n\t" );
if ( scanf( "%d", &option ) == EOF )break;
switch ( option ) {case 1:printf( "Please enter the integer: " );if ( scanf( "%d", &option ) != EOF )printf( "The Hamming Weight of %d ( 0x%X ) is %d\n\n",option, option, bitcount( option ) );break;case 2:printf( "Please select number of reps ( in millions ): " );if ( scanf( "%d", &option ) != EOF )benchmark( option );break;case 3:goto EXIT;break;default:printf( "Invalid option\n" );}
}
EXIT:printf( "\n" );
return 0;}
#endif

Bit Twiddling Hacks

我建议这个：

使用64位指令对14、24或32位字中设置的位进行计数

unsigned int v; // count the number of bits set in vunsigned int c; // c accumulates the total bits set in v
// option 1, for at most 14-bit values in v:c = (v * 0x200040008001ULL & 0x111111111111111ULL) % 0xf;
// option 2, for at most 24-bit values in v:c =  ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL)% 0x1f;
// option 3, for at most 32-bit values in v:c =  ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) %0x1f;c += ((v >> 24) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;

这种方法需要64位CPU快速取模才能高效。第一个选项只需要3次操作；第二个选项需要10次；第三个选项需要15次。

32位还是不32位？我是在阅读了“破解编码面试”第4版练习5.5（第5章：位操作）后于Java提出这种方法的。如果最低有效位是1增量count，则右移整数。

public static int bitCount( int n){int count = 0;for (int i=n; i!=0; i = i >> 1){count += i & 1;}return count;}

我认为这个比常数为0x33333333的解更直观，不管它们有多快。这取决于你对“最佳算法”的定义。

这是示例代码，可能有用。

private static final int[] bitCountArr = new int[]{0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};private static final int firstByteFF = 255;public static final int getCountOfSetBits(int value){int count = 0;for(int i=0;i<4;i++){if(value == 0) break;count += bitCountArr[value & firstByteFF];value >>>= 8;}return count;}

这是在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++另一种选择是使用模板元编程：

// recursive template to sum bits in an inttemplate <int BITS>int countBits(int val) {// return the least significant bit plus the result of calling ourselves with// .. the shifted valuereturn (val & 0x1) + countBits<BITS-1>(val >> 1);}
// template specialisation to terminate the recursion when there's only one bit lefttemplate<>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 )

当然，您可以进一步扩展此模板以使用不同的类型（甚至自动检测位大小），但为了清晰起见，我保持简单。

编辑：忘记提到这是好的，因为它应该在任何C++编译器中工作，如果使用常量值进行位计数，它基本上只是为您展开循环（换句话说，我很确定这是你能找到的最快的通用方法）

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

我个人使用这个：

  public static int myBitCount(long L){int count = 0;while (L != 0) {count++;L ^= L & -L;}return count;}

我使用下面的代码更直观。

int countSetBits(int n) {return !n ? 0 : 1 + countSetBits(n & (n-1));}

逻辑：n&（n-1）重置n的最后设定位。

P. S：我知道这不是O（1）解，尽管这是一个有趣的解。

#!/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=0x11BBBBABB=3 1sA=2 1sso in total1+1+3+3+3+2+3+3=19

你可以这样做：

int countSetBits(int n){n=((n&0xAAAAAAAA)>>1) + (n&0x55555555);n=((n&0xCCCCCCCC)>>2) + (n&0x33333333);n=((n&0xF0F0F0F0)>>4) + (n&0x0F0F0F0F);n=((n&0xFF00FF00)>>8) + (n&0x00FF00FF);return n;}
int main(){int n=10;printf("Number of set bits: %d",countSetBits(n));return 0;}

参见：http://ideone.com/JhwcX

工作可以解释如下：

首先，所有偶数位都向右移动，并与奇数位相加以计算两组中的位数。然后我们两个一组工作，然后四个等等…

unsigned int count_bit(unsigned int x){x = (x & 0x55555555) + ((x >> 1) & 0x55555555);x = (x & 0x33333333) + ((x >> 2) & 0x33333333);x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);x = (x & 0x0000FFFF) + ((x >> 16)& 0x0000FFFF);return x;}

让我解释一下这个算法。

该算法基于分而治之算法。假设有一个8bit整数213（二进制为11010101），该算法的工作原理如下（每次合并两个邻居块）：

+-------------------------------+| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |  <- x|  1 0  |  0 1  |  0 1  |  0 1  |  <- first time merge|    0 0 1 1    |    0 0 1 0    |  <- second time merge|        0 0 0 0 0 1 0 1        |  <- third time ( answer = 00000101 = 5)+-------------------------------+

这不是最快或最好的解决方案，但我以我的方式找到了同样的问题，我开始思考和思考，最后我意识到它可以这样做，如果你从数学方面得到问题，并绘制图表，然后你发现它是一个函数，它有一些周期部分，然后你意识到周期之间的差异……所以在这里你去：

unsigned int f(unsigned int x){switch (x) {case 0:return 0;case 1:return 1;case 2:return 1;case 3:return 2;default:return f(x/4) + f(x%4);}}

我认为最快的方法-不使用查找表和人口数量-如下所示。它只需12次操作即可计算设置位。

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

它之所以有效，是因为您可以通过将其分成两半来计算设置位的总数，计算两半中设置位的数量，然后将它们相加。也称为Divide and Conquer范式。让我们详细介绍一下…

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

两位中的位数可以是0b00、0b01或0b10。让我们尝试在2位上计算出来。

 ---------------------------------------------|   v    |   (v >> 1) & 0b0101   |  v - x   |---------------------------------------------0b00           0b00               0b000b01           0b00               0b010b10           0b01               0b010b11           0b01               0b10

这是需要的：最后一列显示每两位对中的设置位数。如果两位数为>= 2 (0b10)，则and产生0b01，否则产生0b00。

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

这个语句应该很容易理解。在第一次操作之后，我们有每两位的设置位数，现在我们每4位总结该计数。

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) = 0b00000100v + (v >> 4) = 0b01000010 + 0b00000100

它为我们提供了一个字节中设置位的计数，在第二个半字节0b01000110中，因此我们屏蔽了该数字中所有字节的前四个字节（丢弃它们）。

0b01000110 & 0x0F = 0b00000110

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

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

我使用以下函数。我没有检查基准，但它有效。

int msb(int num){int m = 0;for (int i = 16; i > 0; i = i>>1){// debug(i, num, m);if(num>>i){m += i;num>>=i;}}return m;}

这是一个到目前为止还没有提到的解决方案，使用位字段。以下程序使用4种不同的方法对100000000个16位整数数组中的设置位进行计数。定时结果在括号中给出（在MacOSX上，带gcc -O3）：

#include <stdio.h>#include <stdlib.h>
#define LENGTH 100000000
typedef struct {unsigned char bit0 : 1;unsigned char bit1 : 1;unsigned char bit2 : 1;unsigned char bit3 : 1;unsigned char bit4 : 1;unsigned char bit5 : 1;unsigned char bit6 : 1;unsigned char bit7 : 1;} bits;
unsigned char sum_bits(const unsigned char x) {const bits *b = (const bits*) &x;return b->bit0 + b->bit1 + b->bit2 + b->bit3 \+ b->bit4 + b->bit5 + b->bit6 + b->bit7;}
int NumberOfSetBits(int i) {i = i - ((i >> 1) & 0x55555555);i = (i & 0x33333333) + ((i >> 2) & 0x33333333);return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;}
#define out(s) \printf("bits set: %lu\nbits counted: %lu\n", 8*LENGTH*sizeof(short)*3/4, s);
int main(int argc, char **argv) {unsigned long i, s;unsigned short *x = malloc(LENGTH*sizeof(short));unsigned char lut[65536], *p;unsigned short *ps;int *pi;
/* set 3/4 of the bits */for (i=0; i<LENGTH; ++i)x[i] = 0xFFF0;
/* sum_bits (1.772s) */for (i=LENGTH*sizeof(short), p=(unsigned char*) x, s=0; i--; s+=sum_bits(*p++));out(s);
/* NumberOfSetBits (0.404s) */for (i=LENGTH*sizeof(short)/sizeof(int), pi=(int*)x, s=0; i--; s+=NumberOfSetBits(*pi++));out(s);
/* populate lookup table */for (i=0, p=(unsigned char*) &i; i<sizeof(lut); ++i)lut[i] = sum_bits(p[0]) + sum_bits(p[1]);
/* 256-bytes lookup table (0.317s) */for (i=LENGTH*sizeof(short), p=(unsigned char*) x, s=0; i--; s+=lut[*p++]);out(s);
/* 65536-bytes lookup table (0.250s) */for (i=LENGTH, ps=x, s=0; i--; s+=lut[*ps++]);out(s);
free(x);return 0;}

虽然位域版本非常具有可读性，但计时结果显示它比NumberOfSetBits()慢4倍以上。基于查找表的实现仍然要快得多，特别是对于65 kB的表。

当您写出位模式时，Hacker's Delight位摆弄变得更加清晰。

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。

这可以在O(k)中完成，其中k是设置的位数。

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

一个快速的C#解决方案，使用预先计算的字节位计数表，并在输入大小上进行分支。

public static class BitCount{public static uint GetSetBitsCount(uint n){var counts = BYTE_BIT_COUNTS;return n <= 0xff ? counts[n]: n <= 0xffff ? counts[n & 0xff] + counts[n >> 8]: n <= 0xffffff ? counts[n & 0xff] + counts[(n >> 8) & 0xff] + counts[(n >> 16) & 0xff]: counts[n & 0xff] + counts[(n >> 8) & 0xff] + counts[(n >> 16) & 0xff] + counts[(n >> 24) & 0xff];}
public static readonly uint[] BYTE_BIT_COUNTS ={0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};}

int bitcount(unsigned int n){int count=0;while(n){count += n & 0x1u;n >>= 1;}return  count;}

迭代的“计数”与总位数成比例地运行。它只是循环遍历所有位，由于if条件而稍微提前终止。如果1或设置位是稀疏并且在最低有效位之间，则很有用。

我给出了两个算法来回答这个问题，

package countSetBitsInAnInteger;
import java.util.Scanner;
public class UsingLoop {
public static void main(String[] args) {Scanner in = new Scanner(System.in);try {System.out.println("Enter a integer number to check for set bits in it");int n = in.nextInt();System.out.println("Using while loop, we get the number of set bits as: " + usingLoop(n));System.out.println("Using Brain Kernighan's Algorithm, we get the number of set bits as: " + usingBrainKernighan(n));System.out.println("Using ");}finally {in.close();}}
private static int usingBrainKernighan(int n) {int count = 0;while(n > 0) {n& = (n-1);count++;}return count;}
/*Analysis:Time complexity = O(lgn)Space complexity = O(1)*/
private static int usingLoop(int n) {int count = 0;for(int i=0; i<32; i++) {if((n&(1 << i)) != 0)count++;}return count;}
/*Analysis:Time Complexity = O(32) // Maybe the complexity is O(lgn)Space Complexity = O(1)*/}

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年半之后，@PeterMortenen质疑这是否是有效的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;}

public class BinaryCounter {
private int N;
public BinaryCounter(int N) {this.N = N;}
public static void main(String[] args) {
BinaryCounter counter=new BinaryCounter(7);System.out.println("Number of ones is "+ counter.count());
}
public int count(){if(N<=0) return 0;int counter=0;int K = 0;do{K = biggestPowerOfTwoSmallerThan(N);N = N-K;counter++;}while (N != 0);return counter;
}
private int biggestPowerOfTwoSmallerThan(int N) {if(N==1) return 1;for(int i=0;i<N;i++){if(Math.pow(2, i) > N){int power = i-1;return (int) Math.pow(2, power);}}return 0;}}

另一个汉明重锤算法，如果你在一个BMI2能力的CPU：

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

将整数转换为二进制字符串并计数。

PHP解决方案：

substr_count(decbin($integer), '1');

我发现了一个使用SIMD指令（SSSE3和AVX2）在数组中进行位计数的实现。它比使用__popcnt64内在函数具有2-2.5倍的性能。

SSSE3版本：

#include <smmintrin.h>#include <stdint.h>
const __m128i Z = _mm_set1_epi8(0x0);const __m128i F = _mm_set1_epi8(0xF);//Vector with pre-calculated bit count:const __m128i T = _mm_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4);
uint64_t BitCount(const uint8_t * src, size_t size){__m128i _sum =  _mm128_setzero_si128();for (size_t i = 0; i < size; i += 16){//load 16-byte vector__m128i _src = _mm_loadu_si128((__m128i*)(src + i));//get low 4 bit for every byte in vector__m128i lo = _mm_and_si128(_src, F);//sum precalculated value from T_sum = _mm_add_epi64(_sum, _mm_sad_epu8(Z, _mm_shuffle_epi8(T, lo)));//get high 4 bit for every byte in vector__m128i hi = _mm_and_si128(_mm_srli_epi16(_src, 4), F);//sum precalculated value from T_sum = _mm_add_epi64(_sum, _mm_sad_epu8(Z, _mm_shuffle_epi8(T, hi)));}uint64_t sum[2];_mm_storeu_si128((__m128i*)sum, _sum);return sum[0] + sum[1];}

AVX2版本：

#include <immintrin.h>#include <stdint.h>
const __m256i Z = _mm256_set1_epi8(0x0);const __m256i F = _mm256_set1_epi8(0xF);//Vector with pre-calculated bit count:const __m256i T = _mm256_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4);
uint64_t BitCount(const uint8_t * src, size_t size){__m256i _sum =  _mm256_setzero_si256();for (size_t i = 0; i < size; i += 32){//load 32-byte vector__m256i _src = _mm256_loadu_si256((__m256i*)(src + i));//get low 4 bit for every byte in vector__m256i lo = _mm256_and_si256(_src, F);//sum precalculated value from T_sum = _mm256_add_epi64(_sum, _mm256_sad_epu8(Z, _mm256_shuffle_epi8(T, lo)));//get high 4 bit for every byte in vector__m256i hi = _mm256_and_si256(_mm256_srli_epi16(_src, 4), F);//sum precalculated value from T_sum = _mm256_add_epi64(_sum, _mm256_sad_epu8(Z, _mm256_shuffle_epi8(T, hi)));}uint64_t sum[4];_mm256_storeu_si256((__m256i*)sum, _sum);return sum[0] + sum[1] + sum[2] + sum[3];}

我认为Brian Kernighan的方法也很有用…它会经历与设置位一样多的迭代。所以如果我们有一个32位的字，只有高位设置，那么它只会通过一次循环。

int countSetBits(unsigned int n) {unsigned int n; // count the number of bits set in nunsigned int c; // c accumulates the total bits set in nfor (c=0;n>0;n=n&(n-1)) c++;return c;}

发表于1988年的C编程语言第二版（Brian W. Kernighan和Dennis M. Ritchie）在练习2-9中提到了这一点。2006年4月19日，Don Knuth向我指出，这种方法“最初由Peter Wegner在CACM 3（1960），322中发表。（也由Derrick Lehmer独立发现，并于1964年发表在Beckenbach编辑的一本书中。）”

在Java8或9中，只需调用Integer.bitCount。

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

#include <bits/stdc++.h>
using namespace std;
int countOnes(int n) {bitset<32> b(n);return b.count();}

您可以使用名为__builtin_popcount（）的内置函数。C++中no__builtin_popcount，但它是GCC编译器的内置函数。此函数返回整数中的设置位数。

int __builtin_popcount (unsigned int x);

参考：Bit Twiddling Hacks

我在任何地方都没有看到这种方法：

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

它每字节工作，因此对于32位整数必须调用四次。它源自侧向加法，但它使用两次32位乘法将指令数量减少到只有7条。

目前大多数C编译器在明确请求数是4的倍数时，会使用SIMD（SSE2）指令优化这个函数，并且变得相当有竞争力。它是可移植的，可以定义为宏或内联函数，不需要数据表。

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

你可以这样做：

while(n){n = n & (n-1);count++;}

这背后的逻辑是n-1的位从n的最右设置位反转。

如果n=6，即110，则5是101，则位从n的最右边设置位反转。

因此，如果我们&这两个，我们将在每次迭代中将最右边的位0，并始终转到下一个最右边的设置位。因此，计算设置位。当每个位都设置时，最差的时间复杂度将是O（log n）。

private int get_bits_set(int v){int c; // 'c' accumulates the total bits set in 'v'for (c = 0; v>0; c++){v &= v - 1; // Clear the least significant bit set}return c;}

这也将工作得很好：

int ans = 0;while(num) {ans += (num & 1);num = num >> 1;}return ans;

计算设置位数的简单算法：

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

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

C++20std::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仍然不支持它。

该提案说：

标题：<bit>

namespace std {
// 25.5.6, countingtemplate<class T>constexpr int popcount(T x) noexcept;

和：

template<class T>constexpr int popcount(T x) noexcept;

约束：T是无符号整数类型（3.9.1[basic.fundamental]）。

返回：x值中1位的个数。

std::rotl和std::rotr也被添加到循环位旋转中：C++中循环移位（旋转）操作的最佳实践

这是Go语言的实现

func CountBitSet(n int) int {

count := 0for n > 0 {count += n & 1n >>= 1
}return count}

def hammingWeight(n):count = 0while n:if n&1:count += 1n >>= 1return count

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

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

这是函数主竞赛递归解决方案，它是迄今为止最纯粹的解决方案（并且可以与任何位长一起使用！）：

template<typename T>int popcnt(T n){if (n>0)return n&1 + popcnt(n>>1);return 0;}

对于Java，有一个java.util.BitSet。https://docs.oracle.com/javase/8/docs/api/java/util/BitSet.html

cardinality（）：返回此BitSet中设置为true的位数。

BitSet是内存高效的，因为它存储为Long。

Python解决方案：

def hammingWeight(n: int) -> int:sums = 0while (n!=0):sums+=1n = n &(n-1)
return sums

在二进制表示中，n中最低有效的1位总是对应于n-1中的0位。因此，对两个数n和n-1进行处理总是将n中最低有效的1位翻转为0，并保持所有其他位相同。

我提供了另一个未提及的算法，称为并行，取从这里。它的优点是它是通用的，这意味着代码对于位大小8、16、32、64和128是相同的。

我检查了它的值和时序的正确性，对于位大小为8、16、32和64的2^26个数字。请参阅下面的时序。

这个算法是第一个代码片段。这里提到的其他两个只是供参考，因为我测试并比较了它们。

算法以C++编码，是通用的，但它可以很容易地采用到旧的C。

#include <type_traits>#include <cstdint>
template <typename IntT>inline size_t PopCntParallel(IntT n) {// https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallelusing T = std::make_unsigned_t<IntT>;
T v = T(n);v = v - ((v >> 1) & (T)~(T)0/3);                           // tempv = (v & (T)~(T)0/15*3) + ((v >> 2) & (T)~(T)0/15*3);      // tempv = (v + (v >> 4)) & (T)~(T)0/255*15;                      // tempreturn size_t((T)(v * ((T)~(T)0/255)) >> (sizeof(T) - 1) * 8); // count}

下面是我比较的两个算法。一个是带有循环的Kernighan简单方法，取自这里。

template <typename IntT>inline size_t PopCntKernighan(IntT n) {// http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighanusing T = std::make_unsigned_t<IntT>;T v = T(n);size_t c;for (c = 0; v; ++c)v &= v - 1; // Clear the least significant bit setreturn c;}

另一个是使用内置的__popcnt16()/__popcnt()/__popcnt64() MSVC的内部（这里的医生）。或CLang/GCC的__builtin_popcount（这里的医生）。此内部应该提供非常优化的版本，可能是硬件：

#ifdef _MSC_VER// https://learn.microsoft.com/en-us/cpp/intrinsics/popcnt16-popcnt-popcnt64?view=msvc-160#include <intrin.h>#define popcnt16 __popcnt16#define popcnt32 __popcnt#define popcnt64 __popcnt64#else// https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#define popcnt16 __builtin_popcount#define popcnt32 __builtin_popcount#define popcnt64 __builtin_popcountll#endif
template <typename IntT>inline size_t PopCntBuiltin(IntT n) {using T = std::make_unsigned_t<IntT>;T v = T(n);if constexpr(sizeof(IntT) <= 2)return popcnt16(uint16_t(v));else if constexpr(sizeof(IntT) <= 4)return popcnt32(uint32_t(v));else if constexpr(sizeof(IntT) <= 8)return popcnt64(uint64_t(v));elsestatic_assert([]{ return false; }());}

以下是每个数字的计时，以纳秒为单位。所有计时都是针对2^26个随机数完成的。比较了所有三种算法的计时以及8、16、32和64之间的所有位大小。总之，所有测试在我的机器上花费了16秒。使用了高分辨率时钟。

08 bit Builtin 8.2 ns08 bit Parallel 8.2 ns08 bit Kernighan 26.7 ns
16 bit Builtin 7.7 ns16 bit Parallel 7.7 ns16 bit Kernighan 39.7 ns
32 bit Builtin 7.0 ns32 bit Parallel 7.0 ns32 bit Kernighan 47.9 ns
64 bit Builtin 7.5 ns64 bit Parallel 7.5 ns64 bit Kernighan 59.4 ns
128 bit Builtin 7.8 ns128 bit Parallel 13.8 ns128 bit Kernighan 127.6 ns

可以看出，所提供的并行算法（三个算法中的第一个）与MSVC/CLang的内在算法一样好。

作为参考，下面是我用来测试所有函数的速度/时间/正确性的完整代码。

作为奖励，此代码（与上面的短代码片段不同）还测试128位大小，但仅在CLang/GCC（不是MSVC）下，因为它们具有unsigned __int128。

试试在线！

#include <type_traits>#include <cstdint>
using std::size_t;
#if defined(_MSC_VER) && !defined(__clang__)#define IS_MSVC 1#else#define IS_MSVC 0#endif
#if IS_MSVC#define HAS128 false#elseusing int128_t = __int128;using uint128_t = unsigned __int128;#define HAS128 true#endif
template <typename T> struct UnSignedT { using type = std::make_unsigned_t<T>; };#if HAS128template <> struct UnSignedT<int128_t> { using type = uint128_t; };template <> struct UnSignedT<uint128_t> { using type = uint128_t; };#endiftemplate <typename T> using UnSigned = typename UnSignedT<T>::type;
template <typename IntT>inline size_t PopCntParallel(IntT n) {// https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallelusing T = UnSigned<IntT>;
T v = T(n);v = v - ((v >> 1) & (T)~(T)0/3);                           // tempv = (v & (T)~(T)0/15*3) + ((v >> 2) & (T)~(T)0/15*3);      // tempv = (v + (v >> 4)) & (T)~(T)0/255*15;                      // tempreturn size_t((T)(v * ((T)~(T)0/255)) >> (sizeof(T) - 1) * 8); // count}
template <typename IntT>inline size_t PopCntKernighan(IntT n) {// http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighanusing T = UnSigned<IntT>;T v = T(n);size_t c;for (c = 0; v; ++c)v &= v - 1; // Clear the least significant bit setreturn c;}
#if IS_MSVC// https://learn.microsoft.com/en-us/cpp/intrinsics/popcnt16-popcnt-popcnt64?view=msvc-160#include <intrin.h>#define popcnt16 __popcnt16#define popcnt32 __popcnt#define popcnt64 __popcnt64#else// https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#define popcnt16 __builtin_popcount#define popcnt32 __builtin_popcount#define popcnt64 __builtin_popcountll#endif
#define popcnt128(x) (popcnt64(uint64_t(x)) + popcnt64(uint64_t(x >> 64)))
template <typename IntT>inline size_t PopCntBuiltin(IntT n) {using T = UnSigned<IntT>;T v = T(n);if constexpr(sizeof(IntT) <= 2)return popcnt16(uint16_t(v));else if constexpr(sizeof(IntT) <= 4)return popcnt32(uint32_t(v));else if constexpr(sizeof(IntT) <= 8)return popcnt64(uint64_t(v));else if constexpr(sizeof(IntT) <= 16)return popcnt128(uint128_t(v));elsestatic_assert([]{ return false; }());}
#include <random>#include <vector>#include <chrono>#include <string>#include <iostream>#include <iomanip>#include <map>
inline double Time() {static auto const gtb = std::chrono::high_resolution_clock::now();return std::chrono::duration_cast<std::chrono::duration<double>>(std::chrono::high_resolution_clock::now() - gtb).count();}
template <typename T, typename F>void Test(std::string const & name, F f) {std::mt19937_64 rng{123};size_t constexpr bit_size = sizeof(T) * 8, ntests = 1 << 6, nnums = 1 << 14;std::vector<T> nums(nnums);for (size_t i = 0; i < nnums; ++i)nums[i] = T(rng() % ~T(0));static std::map<size_t, size_t> times;double min_time = 1000;for (size_t i = 0; i < ntests; ++i) {double timer = Time();size_t sum = 0;for (size_t j = 0; j < nnums; j += 4)sum += f(nums[j + 0]) + f(nums[j + 1]) + f(nums[j + 2]) + f(nums[j + 3]);auto volatile vsum = sum;min_time = std::min(min_time, (Time() - timer) / nnums);if (times.count(bit_size) && times.at(bit_size) != sum)std::cout << "Wrong bit cnt checksum!" << std::endl;times[bit_size] = sum;}std::cout << std::setw(2) << std::setfill('0') << bit_size<< " bit " << name << " " << std::fixed << std::setprecision(1)<< min_time * 1000000000 << " ns" << std::endl;}
int main() {#define TEST(T) \Test<T>("Builtin", PopCntBuiltin<T>); \Test<T>("Parallel", PopCntParallel<T>); \Test<T>("Kernighan", PopCntKernighan<T>); \std::cout << std::endl;    
TEST(uint8_t); TEST(uint16_t); TEST(uint32_t); TEST(uint64_t);#if HAS128TEST(uint128_t);#endif    
#undef TEST}

静态编程语言 pre1.4

        fun NumberOfSetBits(i: Int): Int {var i = ii -= (i ushr 1 and 0x55555555)i = (i and 0x33333333) + (i ushr 2 and 0x33333333)return (i + (i ushr 4) and 0x0F0F0F0F) * 0x01010101 ushr 24}

这或多或少是在最高答案中看到的答案的副本。

它具有Java修复，然后使用IntelliJ IDEA社区版中的转换器进行转换

1.4及以后（截至2021-05-05-未来可能会改变）。

        fun NumberOfSetBits(i: Int): Int {return i.countOneBits()}

在引擎盖下，它使用Integer.bitCount，如下所示：

@SinceKotlin("1.4")@WasExperimental(ExperimentalStdlibApi::class)@kotlin.internal.InlineOnlypublic actual inline fun Int.countOneBits(): Int = Integer.bitCount(this)

朴素解决方案

时间复杂度为O（n中的位数）

int countSet(unsigned int n){int res=0;while(n!=0){res += (n&1);n >>= 1;      // logical right shift, like C unsigned or Java >>>}return res;}

Brian Kerningam的算法

时间复杂度为O（n中没有设置位）

int countSet(unsigned int n){int res=0;while(n != 0){n = (n & (n-1));res++;}return res;}

32位数字的查找表方法-在这个方法中，我们将32位数字分成四个8位数字的块

时间复杂度为O（1）

static unsigned char table[256]; /* the table size is 256,the number of values i&0xFF (8 bits) can have */
void initialize() //holds the number of set bits from 0 to 255{table[0]=0;for(unsigned int i=1;i<256;i++)table[i]=(i&1)+table[i>>1];}
int countSet(unsigned int n){// 0xff is hexadecimal representation of 8 set bits.int res=table[n & 0xff];n=n>>8;res=res+ table[n & 0xff];n=n>>8;res=res+ table[n & 0xff];n=n>>8;res=res+ table[n & 0xff];return res;}

对于那些希望在C++11中将任何无符号整数类型作为consextr函数（处理/包括/处理/实用程序/math.hpp）的人：

#include <stdint.h>#include <limits>#include <type_traits>
const constexpr uint32_t uint32_max = (std::numeric_limits<uint32_t>::max)();
namespace detail{template <typename T>inline constexpr T _count_bits_0(const T & v){return v - ((v >> 1) & 0x55555555);}
template <typename T>inline constexpr T _count_bits_1(const T & v){return (v & 0x33333333) + ((v >> 2) & 0x33333333);}
template <typename T>inline constexpr T _count_bits_2(const T & v){return (v + (v >> 4)) & 0x0F0F0F0F;}
template <typename T>inline constexpr T _count_bits_3(const T & v){return v + (v >> 8);}
template <typename T>inline constexpr T _count_bits_4(const T & v){return v + (v >> 16);}
template <typename T>inline constexpr T _count_bits_5(const T & v){return v & 0x0000003F;}
template <typename T, bool greater_than_uint32>struct _impl{static inline constexpr T _count_bits_with_shift(const T & v){returndetail::_count_bits_5(detail::_count_bits_4(detail::_count_bits_3(detail::_count_bits_2(detail::_count_bits_1(detail::_count_bits_0(v)))))) + count_bits(v >> 32);}};
template <typename T>struct _impl<T, false>{static inline constexpr T _count_bits_with_shift(const T & v){return 0;}};}
template <typename T>inline constexpr T count_bits(const T & v){static_assert(std::is_integral<T>::value, "type T must be an integer");static_assert(!std::is_signed<T>::value, "type T must be not signed");
return uint32_max >= v ?detail::_count_bits_5(detail::_count_bits_4(detail::_count_bits_3(detail::_count_bits_2(detail::_count_bits_1(detail::_count_bits_0(v)))))) :detail::_impl<T, sizeof(uint32_t) < sizeof(v)>::_count_bits_with_shift(v);}

Google测试库中的附加测试：

#include <stdlib.h>#include <time.h>
namespace {template <typename T>inline uint32_t _test_count_bits(const T & v){uint32_t count = 0;T n = v;while (n > 0) {if (n % 2) {count += 1;}n /= 2;}return count;}}
TEST(FunctionsTest, random_count_bits_uint32_100K){srand(uint_t(time(NULL)));for (uint32_t i = 0; i < 100000; i++) {const uint32_t r = uint32_t(rand()) + (uint32_t(rand()) << 16);ASSERT_EQ(_test_count_bits(r), count_bits(r));}}
TEST(FunctionsTest, random_count_bits_uint64_100K){srand(uint_t(time(NULL)));for (uint32_t i = 0; i < 100000; i++) {const uint64_t r = uint64_t(rand()) + (uint64_t(rand()) << 16) + (uint64_t(rand()) << 32) + (uint64_t(rand()) << 48);ASSERT_EQ(_test_count_bits(r), count_bits(r));}}

以二进制表示（N）计数设置位：

伪代码-

1. 设置计数器=0。

2. 重复计数直到N不为零。

3. 检查最后一位。如果最后一位=1，则递增计数器

4. 丢弃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）设置。

您可以运行代码这里。

对于JavaScript，您可以使用查找表计算32位值的设置位数（并且此代码可以轻松翻译为C）。此外，添加了8位和16位版本，以确保通过Web搜索找到此内容的人的完整性。

const COUNT_BITS_TABLE = makeLookupTable()
function makeLookupTable() {const table = new Uint8Array(256)for (let i = 0; i < 256; i++) {table[i] = (i & 1) + table[(i / 2) | 0];}return table}
function countOneBits32(n) {return COUNT_BITS_TABLE[n & 0xff] +COUNT_BITS_TABLE[(n >> 8) & 0xff] +COUNT_BITS_TABLE[(n >> 16) & 0xff] +COUNT_BITS_TABLE[(n >> 24) & 0xff];}
function countOneBits16(n) {return COUNT_BITS_TABLE[n & 0xff] +COUNT_BITS_TABLE[(n >> 8) & 0xff]}
function countOneBits8(n) {return COUNT_BITS_TABLE[n & 0xff]}
console.log('countOneBits32', countOneBits32(0b10101010000000001010101000000000))console.log('countOneBits32', countOneBits32(0b10101011110000001010101000000000))console.log('countOneBits16', countOneBits16(0b1010101000000000))console.log('countOneBits8', countOneBits8(0b10000010))