在一个32位整数中计算二进制位为1的数量

Question

表示数字7的8位二进制数如下：

00000111

有三个二进制位被设置为1。

如何确定32位整数中设置位的数量所使用的算法？

- Matt Howells

---

这是汉明重量，顺便说一下。 - Purfideas

有什么现实世界的应用吗？（这不是批评，我只是好奇。） - jonmorgan

奇偶校验位（请查询），它被用作通信中简单的错误检测。 - Dialecticus

@Dialecticus，计算奇偶校验位比计算汉明重量更省资源。 - finnw

假设你有一个用邻接矩阵表示的图，它本质上是一个位集合。如果你想计算一个顶点的边数，就需要计算位集合中一行的汉明重量。 - fuz

Answer 1

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

一些CPU具有单个内置指令来执行此操作，而其他CPU具有作用于位向量的并行指令。在支持的CPU上，像x86的popcnt（几乎肯定是最快的单个整数操作）这样的指令将是最快的。其他一些体系结构可能会使用一个微码循环来实现一个慢速指令，每个周期测试一个位（需要引用-如果存在硬件popcount，通常很快）。

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

你的编译器可能知道如何为你编译的特定CPU做一些好事，例如C++20的std::popcount()或C++的std::bitset<32>::count()，作为一种便携式访问内置/内部函数的方式（请参见这个问题的另一个答案）。但是，对于没有硬件popcnt的目标CPU，你的编译器选择的后备方案可能不适合你的用例。或者你的编程语言（例如C）可能没有公开任何便携式函数，可以在有时使用特定于CPU的popcount。

---

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

如果您的CPU具有大容量缓存并且在紧密循环中执行大量此类操作，预填充的表查找方法可以非常快速。然而，由于“缓存未命中”的开销，它可能会受到影响，其中CPU必须从主存中获取一些表的内容。（单独查找每个字节以保持表的小型化。）如果您想要对连续范围的数字进行popcount计算，只有低字节在256个数字组中发生变化，这样非常好。

如果您知道字节主要是0或1，则针对这些情况有高效的算法，例如在循环中使用位操作清除最低位，直到变为零。

我相信以下是一个非常好的通用算法，被称为“并行”或“可变精度SWAR算法”。我用类似C的伪代码表达了这个算法，您可能需要根据特定语言进行调整（例如，在C++中使用uint32_t，在Java中使用>>>）：

GCC10和clang 10.0可以识别这种模式/习语，并在可用时将其编译为硬件popcnt或等效指令，为您提供两全其美的选择。 (Godbolt)

int numberOfSetBits(uint32_t i)
{
     // Java: use int, and use >>> instead of >>. Or use Integer.bitCount()
     // C or C++: use uint32_t
     i = i - ((i >> 1) & 0x55555555);        // add pairs of bits
     i = (i & 0x33333333) + ((i >> 2) & 0x33333333);  // quads
     i = (i + (i >> 4)) & 0x0F0F0F0F;        // groups of 8
     i *= 0x01010101;                        // horizontal sum of bytes
     return  i >> 24;               // return just that top byte (after truncating to 32-bit even when int is wider than uint32_t)
}

对于JavaScript：为了提高性能，使用|0将其强制转换为整数：将第一行改为i = (i|0) - ((i >> 1) & 0x55555555); 这是讨论的算法中具有最好的最坏情况行为，因此它能有效地处理任何使用模式或值。在普通的CPU上，它的性能不依赖于数据，包括乘法在内的所有整数操作都是恒定时间。它在"简单"输入上不会变得更快，但仍然相当不错。

参考资料：

• 位操作技巧
• 低级位操作入门，了解位操作的基础知识，比如减1会翻转连续的零。
• 汉明重量（维基百科）
• 快速位计数
• 聚合魔术算法

---

这个SWAR bithack是如何工作的：

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

第一步是对掩码进行优化，以隔离奇偶位，将它们移动并相加。这实际上在2位累加器中进行了16次单独的相加操作（SWAR = SIMD Within A Register）。就像(i & 0x55555555) + ((i>>1) & 0x55555555)。

下一步是对这16个2位累加器中的奇偶八位再次相加，得到8个4位和。这次无法使用i - ...优化，所以只需在移位前/后进行掩码操作。在编译需要单独构建32位常量的ISA时，两次使用相同的0x33...常量而不是0xccc...常量是一件好事。

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

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

一旦我们的"元素"足够少，一个与魔术常数相乘的操作就能将所有元素相加到顶部元素。在这种情况下，元素是字节。乘法通过左移和加法完成，所以 x * 0x01010101 的乘法结果是 x + (x<<8) + (x<<16) + (x<<24)。我们的8位元素足够宽（并且包含的计数足够小），这样就不会产生进位到顶部8位的情况。

这个方法的64位版本可以在64位整数中处理8个8位元素，使用0x0101010101010101作为乘数，并通过右移56来提取高字节。因此，它不需要额外的步骤，只需要更宽的常数。这就是GCC在x86系统上使用的__builtin_popcountll，当硬件popcnt指令未启用时。如果可以使用内建函数或内部函数来完成这个操作，请这样做，以便让编译器有机会进行针对特定目标的优化。

---

具有完整的SIMD以支持更宽的向量（例如对整个数组进行计数）。

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

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

在Intel CPU上，硬件64位popcnt指令可以比一个SSSE3 PSHUFB位并行实现快大约2倍，但前提是你的编译器要正确使用它。否则，SSE可能会更快。较新版本的编译器已经意识到了在Intel上的popcnt错误依赖问题。

• 先进的x86 SIMD popcount适用于SSSE3、AVX2、AVX512BW、AVX512VBMI或AVX512 VPOPCNT。使用Harley-Seal跨向量延迟元素内的popcount。（还有ARM NEON）
• 使用AVX-512或AVX-2对大数据进行1位计数（人口统计）
• 相关：mklarqvist的位置popcount-多个8、16、32或64位整数的每个位位置的单独计数。（同样，x86 SIMD包括非常擅长此操作的AVX-512，使用vpternlogd使Harley-Seal非常好。）

- Matt Howells

---

哈！喜欢 NumberOfSetBits() 函数，但是通过代码审查可能有点困难。 :-) - Jason S

也许应该使用 unsigned int，以便轻松表明它没有任何符号位的复杂性。此外，使用 uint32_t 是否更安全，即在所有平台上都能得到您所期望的结果？ - Craig McQueen

实际上，按照现有的写法，这段代码存在漏洞并需要维护。对于负数，>> 的行为是由具体实现定义的。参数需要被更改（或强制转换）为 unsigned类型，并且由于该代码只针对32位特定情况，应该使用 uint32_t。 - R.. GitHub STOP HELPING ICE

这并不是真正的魔法。它是通过一些巧妙的优化，将一组比特加起来得出结果。回答中给出的维基百科链接很好地解释了这个过程，但我会逐行解释。1) 计算每对比特中比特数的总和，并将该计数放入该比特对中（你会得到00、01或10）;这里的“巧妙”之处在于减去避免了一个掩码。2) 将这些比特对的总和成对添加到它们对应的半字节中；这里没有什么巧妙的地方，但每个半字节现在将具有0-4的值。（续） - dash-tom-bang

另外需要注意的是，通过适当扩展常量，这也适用于64位和128位寄存器。有趣的是（对我来说），这些常量也是~0 / 3、5、17和255；前三个是2^n+1。如果你在淋浴时多盯着它看并思考一下，这一切就会更有意义。 :) - dash-tom-bang

Answer 2

一些语言以可移植的方式暴露操作，如果有的话，可以使用高效的硬件支持，否则会使用一些库回退，希望是合理的。

例如（来自语言对比表）：

- C++有`std::bitset<>::count()`，或者C++20的`std::popcount(T x)` - Java有`java.lang.Integer.bitCount()`（也适用于Long或BigInteger） - C#有`System.Numerics.BitOperations.PopCount()` - Python有`int.bit_count()`（自3.10版本起）

然而，并非所有的编译器/库在有硬件支持时都能够使用它（尤其是MSVC，即使使用了使std::popcount内联为x86 popcnt的选项，其std::bitset::count仍然始终使用查找表。希望在未来的版本中能够改变这一点）。

当便携语言缺乏基本位操作时，还要考虑编译器的内置函数。例如，在GNU C中：

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

在最糟糕的情况下（没有单指令硬件支持），编译器将生成一个对函数的调用（在当前的GCC中，它使用了一个移位/与位操作的技巧，类似于这个答案）。在最好的情况下，编译器将发出一个CPU指令来完成任务（就像一个*或/运算符 - 如果有的话，GCC将使用硬件乘法或除法指令，否则将调用一个libgcc辅助函数）。或者更好的是，如果操作数是一个编译时常量，在内联之后，它可以进行常量传播以获得一个编译时常量的popcount结果。

GCC内置函数甚至可以跨多个平台使用。在x86架构中，popcount几乎已经成为主流，所以现在开始使用内置函数是有意义的，这样当您使用-mpopcnt或包含该选项时重新编译时，它可以内联一个硬件指令（例如）。其他架构多年来一直有popcount，但在x86世界中，仍然有一些古老的Core 2和类似的AMD CPU在使用中。

---

在x86上，你可以告诉编译器它可以假设支持popcnt指令，使用-mpopcnt（也可以通过-msse4.2隐含地支持）。请参考GCC x86选项。选择-march=nehalem -mtune=skylake（或者选择你想要代码假设和优化的CPU）可能是一个不错的选择。在旧的CPU上运行生成的二进制文件将导致非法指令错误。

为了使二进制文件针对构建它们的机器进行优化，使用-march=native（使用gcc、clang或ICC）。 MSVC为x86的popcnt指令提供了内置函数，但与gcc不同，它实际上是针对硬件指令的内置函数，需要硬件支持。

---

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

理论上，任何能够高效地计算目标CPU的popcount的编译器都应该通过ISO C++ std::bitset<>来暴露这个功能。实际上，在某些情况下，对于某些目标CPU，使用位操作的AND/shift/ADD可能更好。

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

但至少你可以获得在任何地方都能正常工作的可移植性，而且对于支持的架构，使用正确的目标选项，你可以获得硬件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();
}

See asm from gcc, clang, icc, and MSVC on the Godbolt compiler explorer.

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 参数版本）如下：

    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）时如此。

还要注意，gcc对于没有单指令popcount的架构的回退是逐字节的表查找。这对于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 现场演示

# 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），它也能很好地运行。在线演示

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

- Nils

---

我同意这通常是一个很好的实践，但在XCode/OSX/Intel上，我发现它生成的代码比这里发布的大多数建议要慢。有关详细信息，请参阅我的回答。 - Mike F

Intel i5/i7拥有SSE4指令POPCNT，可以使用通用寄存器执行。在我的系统上，GCC没有使用这个内置函数来发出该指令，我猜是因为尚未使用-march=nehalem选项。 - matja

如果我使用 -msse4.2 编译，我的 GCC 4.4.1 会发出 popcnt 指令。 - Nils Pipenbrinck

使用 C++ 的 std::bitset::count。将其内联后，编译器会将其优化为单个 __builtin_popcount 调用。 - deft_code

@nlucaroni 嗯，是的。时代在变化。我在2008年写了这个答案。现在我们有本地popcount，如果平台允许，内在函数将编译成单个汇编语句。 - Nils Pipenbrinck

Answer 3

在我看来，“最好”的解决方案是另一个程序员（或原始程序员两年后）可以阅读而不需要大量注释的解决方案。你可能想要最快或者最聪明的解决方案，但我更喜欢可读性而非聪明。

unsigned int bitCount (unsigned int value) {
    unsigned int count = 0;
    while (value > 0) {           // until all bits are zero
        if ((value & 1) == 1)     // check lower bit
            count++;
        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, // 0n
    1, 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);
}

这些依赖于特定的数据类型大小，因此它们并不是那么易携带。但是，由于许多性能优化本身就不可移植，所以这可能不是一个问题。如果您想要可移植性，我建议使用易读的解决方案。

- Pax Diablo

---

不要将除以2并注释为“位移...”的代码留下，而应该直接使用移位运算符（>>）并删除注释。 - indiv

将 if ((value & 1) == 1) { count++; } 替换为 count += value & 1，会更加合理易懂。这样不会改变原意。 - Ponkadoodle

不，这种情况下最好的解决方案并不是最易读的那一个。在这里，最好的算法是最快的那个。 - NikiC

那完全是你的看法，@nikic，虽然你自然可以给我点踩。问题中没有提及如何量化“最好”，也没有出现“性能”或“快速”这些词。因此我选择了“易读性”。 - paxdiablo

我已经清楚地表明，我的答案严重基于我的观点和偏好，我认为重新阐述已经在进行中的基于表现的答案是没有必要的。早期的评论已经涵盖了这方面的问题，显然有172人同意，尽管这只占了Stack Overflow社区很小一部分的四分之四，因此可能并不那么重要 :-) 。总之，我对您投票的方式没有任何问题，我只是想确保您和其他人至少理解我给出这个答案的原因。如果您愿意，您可以说最后一句话，我认为我已经尽力解释清楚了。 - paxdiablo

Answer 4

来自《黑客的乐趣》，第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个指令（与架构有关）内执行，没有分支。

Hacker's Delight 这本书真是太好了! 强烈推荐。

- Kevin Little

---

Java方法Integer.bitCount(int)使用完全相同的实现。 - Marco Bolis

我有一些困难理解这个 - 如果我们只关心16位值而不是32位，它将如何改变？ - Jeremy Blum

也许“hackers delight”很令人愉悦，但是如果有人称之为“pop”而不是“population_count”（或者如果你必须缩写，则为“pop_cnt”），我会给他们一个好的踢。@MarcoBolis，我认为这对所有版本的Java都是正确的，但官方上来说这取决于具体实现 :) - Maarten Bodewes

而且，这不需要像被接受的答案中的代码那样进行乘法运算。 - Alex

请注意，在推广到64位时存在一个问题。由于掩码的存在，结果不能为64。 - Albert van der Horst

@Alex: 这段代码的第一部分与被接受的答案是相同的，它只是使用了多个两次移位加法步骤，将4个字节水平求和为1个字节，而不是通过乘以一个0x01010101常量将所有4个字节加总到高字节中。 （我会先执行x>>16部分，使缩小工作通过两次缩小有价值的部分来进行。）在没有快速乘法器的CPU上，这是可取的（特别是如果它可以有效地进行大移位，而不是像每个周期1位那样。或者如果它有其他提取高半部分的方法；例如，在16位CPU上，它已经被拆分了）。 - Peter Cordes

Answer 5

我认为最快的方法，不使用查找表和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。让我们试着在两个比特上计算一下。

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

这就是所需的内容：最后一列显示了每个两位数对中设置位的计数。如果两位数>= 2 (0b10)，则and生成0b01，否则生成0b00。

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

这个语句应该很容易理解。在第一次操作后，我们得到了每两位中集合位的计数，现在我们在每四位中总计这个计数。

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

这给出了一个字节中集合位的计数，例如在第二个半字节 0b01000110 中，因此我们屏蔽掉数字中所有字节的前四个字节（将其丢弃）。

0b01000110 & 0x0F = 0b00000110

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

现在我们所需要的是第一个字节，它包含所有字节中设置的位数总和，并通过>> 24获得。此算法设计用于32位字，但可以轻松修改为64位字。

- vidit

---

c = 是什么意思？似乎应该被删除。此外，建议添加一组括号A"(((v + (v >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24"以避免一些经典的警告。 - chux - Reinstate Monica

一个重要的特性是这个32位程序可以同时用于popcount(int v)和popcount(unsigned v)。为了提高可移植性，请考虑使用popcount(uint32_t v)等类型。我真的很喜欢*0x1010101这部分。 - chux - Reinstate Monica

酱料？（书籍、链接、发明者姓名等）将非常受欢迎。因为这样我们就可以在代码库中粘贴它，并注明它的来源。 - v.oddou

我认为为了更清晰，最后一行应该写成： return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24; 这样我们就不需要数字母来看你实际上在做什么（因为你丢弃了第一个 0，我不小心以为你使用了错误的（翻转的）位模式作为掩码 - 直到我注意到只有7个字母而不是8个）。 - emem

@GeorgeKoehler：通常情况下，乘法比加法的延迟要高，但对于吞吐量来说，它通常仍然是管道中的单个插槽。因此，乱序执行仍然可以将其与周围的代码重叠。但将4个字节相加到1个字节的替代方法是两个移位和2个加法，就像Hacker's Delight答案中所述，这与本答案和被接受的答案相同，直到最后的缩减步骤。 - Peter Cordes

Answer 6

如果您正在使用Java，内置方法Integer.bitCount可以实现此功能。

- Noether

---

当Sun提供不同的API时，它一定是在后台使用某些逻辑，对吧？ - Vallabh Patade

顺便提一下，Java的实现使用了由Kevin Little指出的相同算法。 - Marco Bolis

除了实现方式之外，这可能是维护您代码的开发人员（在您离开后或6个月后回来时）最清晰的意图信息。 - divillysausages

Answer 7

我感到无聊，于是计时了三种方法的十亿次迭代。编译器为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，则使用第二种方法。否则，请使用可读性较差（但速度较慢）的逐位计算方法。

很难想象您会想使用位操作的方法。

编辑：类似的结果在这里。

- Mike F

---

@Mike，如果表格在缓存中，基于表格的方法是无法匹敌的。这种情况在微基准测试（例如，在紧密循环中进行数百万次测试）中经常出现。然而，缓存未命中需要约200个周期，即使是最简单的popcount也会更快。这总是取决于应用程序。 - Nils Pipenbrinck

如果你不会在一个紧密循环中调用这个程序几百万次，那么你根本没有理由关心它的性能，而且最好使用朴素但易读的方法，因为性能损失将是微不足道的。此外，顺便提一下，8位查找表在10-20次调用内就会缓存热。 - Mike F

我认为很容易想象出这样一种情况：在你的应用程序中，这是从实际执行重要任务的方法中发出的叶子调用。根据其他正在发生的事情（和线程），较小的版本可能会胜出。许多算法由于更好的引用局部性而超越同行。为什么这个不能呢？ - Jason

除非使用了-msse4.2选项，否则GCC不会生成popcnt指令，而这种情况比“横向加法”更快。 - lvella

查找一个单词怎么样？ - HelloGoodbye

Answer 8

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

让我来解释一下这个算法。

这个算法基于分治算法。假设有一个8位整数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)
+-------------------------------+

- abcdabcd987

---

这个算法是Matt Howells发布的版本，在被优化之前，该版本已经难以阅读。 - Lefteris E

@LefterisE：除了一直使用移位/加法到最后，而是使用乘法将8位块相加到顶部8位，替换这里的最后2个“x=…”行。我的编辑使其更清晰易读（保留优化逻辑，改善可读性并添加注释），并添加了一个解释SWAR位操作的部分。尽管如此，这个答案仍然有用，至少对于图表来说是这样的。或者对于一个具有缓慢乘法指令的假设32位机器来说也是如此。 - Peter Cordes

Answer 9

这是一个需要了解微架构的问题。我刚刚使用C++内联函数来消除函数调用开销，使用rdtsc进行时序测量（时钟周期精确度），在gcc 4.3.3下编译，采用-O3选项，迭代10亿次，并保持所有计数的运行总和以确保编译器不会删除任何重要部分。

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(unsigned long) == 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 gigacycles / 14.1 gigacycles。后面这个数字加起来有1280亿个比特，并对应于此台机器上经过了5.9秒的时间。非并行版本的速度略微提高，因为我正在64位模式下运行，它比32位寄存器稍微更喜欢64位寄存器。

让我们看看这里是否还有更多的OOO流水线技术可用。 这需要更多的涉及，因此我实际上进行了一些测试。 每个项单独加起来总和为64，所有组合总和为256。

内联函数 int pop4(unsigned long x, unsigned long y, 
                unsigned long u, unsigned long v) {
  枚举 { 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);
    返回 x & 0x000001FF;
}

一开始我很兴奋，但事实证明gcc即使我在某些测试中没有使用inline关键字，也会使用-O3进行嵌入技巧。当我让gcc玩弄技巧时，十亿次对pop4（）的调用需要12.56 gigacycles，但我确定它正在将参数折叠为常数表达式。更现实的数字似乎是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(); 

2560亿位在8.17秒内求和。根据16位表查找中的基准测试，每32 million bit使用1.02秒。不能直接比较，因为另一个基准测试没有给出时钟速度，但看起来我已经击败了64 KB表版，这本来就是对L1缓存的悲惨利用。

更新：决定做显而易见的事情，并通过添加四行重复代码来创建pop6（）。总时间为22.8gc，总共3840亿位在9.5秒内求和。现在每32 billion bits使用800ms。

- user183351

---

我见过的最好的非汇编形式是每次展开24个32位字。http://dalkescientific.com/writings/diary/popcnt.c，https://dev59.com/THA65IYBdhLWcg3wrQl4，http://www.dalkescientific.com/writings/diary/archive/2008/07/05/bitslice_and_popcount.html - Matt Joiner

Answer 10

为什么不能反复除以2？

计数器 = 0
当 n > 0 时
  如果 (n % 2) 等于 1
    计数器加1
  n 除以等于2  

我同意这不是最快的方法，但是“最好”的定义有些模糊。我认为，“最好”应该具有清晰度的元素。

- daniel

---

除非您经常这样做，否则性能影响将微不足道。因此，所有事情都相等，我同意丹尼尔的看法，“最佳”意味着“不像乱码”。 - Mike F

我故意没有定义“最好”，以获得各种方法。让我们面对现实，如果我们已经降到了这种位操作的水平，那么我们可能正在寻找一些超级快速的东西，看起来像黑猩猩打出来的。 - Matt Howells

糟糕的代码。编译器可能会将其改进为良好的代码，但在我的测试中GCC没有这样做。将(n％2)替换为(n&1); 位运算AND比模数运算更快。将(n/=2)替换为(n>>=1); 位移比除法更快。 - Mecki

在我的测试中，gcc（4.0，-O3）确实进行了显而易见的优化。 - Mike F

负数的 n 始终返回 0。 - chux - Reinstate Monica