algorithm - 如何计算 32 位整数中设置的位数？

Question

代表数字 7 的 8 位如下所示：

00000111

设置了三位。

确定 32 位整数中设置位数的算法是什么？

Answer 1

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

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

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

您的编译器可能知道如何为您正在编译的特定 CPU 做一些有益的事情，例如C++20std::popcount()或 C++ std::bitset<32>::count()，作为访问内置/内在函数的可移植方式（请参阅有关此问题的另一个答案）。但是您的编译器为没有硬件 popcnt 的目标 CPU 选择的后备可能不是您的用例的最佳选择。或者您的语言（例如 C）可能不会公开任何可以使用特定于 CPU 的 popcount 的可移植函数。

---

不需要（或受益于）任何硬件支持的可移植算法

如果您的 CPU 有一个大缓存并且您在一个紧密的循环中执行大量这些操作，那么预填充的表查找方法可能会非常快。然而，由于“缓存未命中”的代价，它可能会受到影响，其中 CPU 必须从主内存中获取一些表。（分别查找每个字节以保持表格较小。）如果您希望 popcount 用于连续范围的数字，则只有低字节会改变 256 个数字的组，这非常好。

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

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

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_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
     return (i * 0x01010101) >> 24;          // horizontal sum of bytes
}

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

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

参考：

• https://graphics.stanford.edu/~seander/bithacks.html
• 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(Ones%20Count)

---

这个 SWAR bithack 是如何工作的：

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

第一步是屏蔽的优化版本，以隔离奇数/偶数位，将它们对齐并添加。这有效地在 2 位累加器中进行了 16 次单独的加法（SWAR = SIMD Within A Register）。喜欢(i & 0x55555555) + ((i>>1) & 0x55555555)。

下一步取这些 16x 2 位累加器中的奇数/偶数 8 个并再次相加，产生 8x 4 位和。这次i - ...无法进行优化，因此它只是在移位之前/之后进行掩码。0x33...在为需要分别在寄存器中构造 32 位常量的 ISA 进行编译时，两次而不是在移位之前使用相同的常量0xccc...是一件好事。

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

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

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

64 位版本可以使用 0x0101010101010101 乘法器在 64 位整数中处理 8x 8 位元素，并使用>>56. 所以它不需要任何额外的步骤，只是更广泛的常数。当硬件指令未启用时，这就是 GCC__builtin_popcountll在 x86 系统上的用途。popcnt如果您可以为此使用内置函数或内部函数，请这样做以使编译器有机会进行特定于目标的优化。

---

对更宽的向量使用完整的 SIMD（例如计算整个数组）

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

但是，对 popcount 使用向量指令的最佳方法通常是使用变量混洗对每个字节并行执行 4 位的表查找。（4 位索引保存在向量寄存器中的 16 项表）。

在 Intel CPU 上，硬件 64 位 popcnt 指令的性能可以比SSSE3PSHUFB位并行实现高出大约 2 倍，但前提是您的编译器可以做到恰到好处。否则 SSE 可能会明显领先。较新的编译器版本知道 Intel 上的popcnt 错误依赖 问题。

• https://github.com/WojciechMula/sse-popcount SSSE3、AVX2、AVX512BW、AVX512VBMI 或 AVX512 VPOPCNT 的最新 x86 SIMD 弹出计数。跨向量使用 Harley-Seal 来延迟元素内的 popcount。（还有 ARM NEON）
• 使用 AVX-512 或 AVX-2 对大数据计数 1 位（人口计数）
• 相关：https ://github.com/mklarqvist/positional-popcount - 多个 8、16、32 或 64 位整数的每个位位置的单独计数。（同样，x86 SIMD 包括 AVX-512 非常擅长这一点，vpternlogd让 Harley-Seal非常好。）

Answer 2

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

例如（来自按语言的表）：

• C++ 有std::bitset<>::count(), 或 C++20std::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 中，该函数使用类似于此答案的移位/和位破解，至少对于 x86 而言）。在最好的情况下，编译器会发出一条 cpu 指令来完成这项工作。（就像*or/运算符 - 如果可用，GCC 将使用硬件乘法或除法指令，否则将调用 libgcc 辅助函数。）或者更好的是，如果操作数是内联后的编译时常量，它可以进行常量传播得到一个编译时常数 popcount 结果。

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

---

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

要使二进制文件针对您构建它们的机器进行优化，请使用-march=native （使用 gcc、clang 或 ICC）。

MSVC 为 x86popcnt指令提供了一个内在函数，但与 gcc 不同，它实际上是硬件指令的内在函数，并且需要硬件支持。

---

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

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

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

但至少你得到了一些可移植的东西，可以在任何地方工作，并且使用 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-64gcc -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

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

    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;当为 x86 编译时，clang 不会优化：

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

铿锵声 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 或更高版本（并使用 启用 C++20 -std:c++latest）。https://godbolt.org/z/7K4Gef

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

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

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

Answer 4

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

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

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 c = ((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               0b00   
   0b01           0b00               0b01     
   0b10           0b01               0b01
   0b11           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 个一组来计算设置的位。我们知道——由于我们之前的操作——每个半字节都有设置位的计数。让我们看一个例子。假设我们有 byte 0b01000010。这意味着第一个半字节设置了 4 位，第二个半字节设置了 2 位。现在我们将这些半字节加在一起。

0b01000010 + 0b01000000

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

0b01100010 & 0xF0 = 0b01100000

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

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

Answer 6

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

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，请使用第二种方法。否则，请使用可读（但速度慢）的一次一位的方法。

很难想到您想要使用位旋转方法的情况。

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

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

Answer 9

为什么不迭代地除以 2？

计数 = 0
而 n > 0
  如果 (n % 2) == 1
    计数 += 1
  n /= 2  

我同意这不是最快的，但“最好”有点模棱两可。我会争辩说，“最好”应该有一个清晰的元素

Answer 10

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

内联 int pop2（无符号 x，无符号 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);
    返回 (x+y) & 0x000000FF;
}

未修改的 Hacker's Delight 耗时 12.2 gigacycles。我的并行版本（计算比特数的两倍）以 13.0 千兆周期运行。在 2.4GHz Core Duo 上，两者总共耗时 10.5 秒。25 gigacycles = 在这个时钟频率下刚刚超过 10 秒，所以我相信我的时间安排是正确的。

这与指令依赖链有关，这对这个算法非常不利。通过使用一对 64 位寄存器，我几乎可以再次将速度提高一倍。事实上，如果我很聪明，早一点添加 x+ya，我就可以减少一些班次。进行了一些小调整的 64 位版本的结果差不多，但位数又是原来的两倍。

使用 128 位 SIMD 寄存器，又是两倍，SSE 指令集通常也有巧妙的捷径。

没有理由让代码特别透明。界面简洁，算法多处可在线引用，可进行综合单元测试。偶然发现它的程序员甚至可能学到一些东西。这些位操作在机器级别是非常自然的。

好的，我决定对调整后的 64 位版本进行基准测试。对于这个 sizeof(unsigned long) == 8

内联 int pop2（无符号长 x，无符号长 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);
    返回 x & 0xFF;
}

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

让我们看看这里是否有更多的 OOO 流水线。这涉及到更多，所以我实际上进行了一些测试。每一项单独总和为 64，所有组合总和为 256。

inline 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 正在使用 -O3 玩内联技巧，即使我在某些测试中没有使用 inline 关键字。当我让 gcc 发挥作用时，对 pop4() 的十亿次调用需要 12.56 个千兆周期，但我确定它是将参数折叠为常量表达式。一个更现实的数字似乎是 19.6gc，另外 30% 的加速。我的测试循环现在看起来像这样，确保每个参数都足够不同以阻止 gcc 玩诡计。

   hitime b4 = rdtsc();
   for (无符号长 i = 10L * 1000*1000*1000; i < 11L * 1000*1000*1000; ++i)
      总和 += pop4 (i, i^1, ~i, i|1);
   hitime e4 = rdtsc();

在 8.17 秒内总计 2560 亿位。在 16 位表查找中以 3200 万位为基准，运行时间为 1.02 秒。不能直接比较，因为另一个bench没有给出时钟速度，但是看起来我已经把64KB table edition的鼻涕给拍了出来，这首先是一个悲惨的使用L1缓存。

更新：决定做显而易见的事情并通过添加四个重复的行来创建 pop6()。得出 22.8gc，在 9.5 秒内总计 3840 亿位。所以现在还有 20% 的时间为 800 毫秒，用于 320 亿位。

Answer 11

当您写出位模式时，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。

Answer 12

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

Answer 13

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

int NumberOfSetBits(int n)
{
    int count = 0;

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

    return count;
}

Answer 14

这不是最快或最好的解决方案，但我在我的方式中发现了同样的问题，我开始思考和思考。最后我意识到如果你从数学方面得到问题，然后画一个图，然后你会发现它是一个有一些周期部分的函数，然后你就会意识到周期之间的差异......所以干得好：

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

Answer 15

您正在寻找的函数通常称为二进制数的“横向和”或“人口计数”。Knuth 在前分册 1A，pp11-12 中讨论了它（尽管在第 2 卷，4.6.3-(7) 中有一个简短的参考。）

经典轨迹是 Peter Wegner的文章“A Technique for Counting Ones in a Binary Computer”，来自ACM 通讯，第 3 卷 (1960) 第 5 期，第 322 页。他在那里给出了两种不同的算法，一种针对预期为“稀疏”的数字进行了优化（即，有少量的数字），另一种针对相反的情况。

Answer 16

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

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

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

Answer 17

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

Answer 18

几个未解决的问题：-

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

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

count = 0
while n != 0
if ((n % 2) == 1 || (n % 2) == -1
    count += 1
  n /= 2  
return 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

Answer 19

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

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

逻辑：n & (n-1) 重置 n 的最后一个设置位。

PS：我知道这不是 O(1) 解决方案，尽管它是一个有趣的解决方案。

Answer 20

“最佳算法”是什么意思？短代码还是禁食代码？您的代码看起来非常优雅，并且执行时间恒定。代码也很短。

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

       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 位值可以更快。

Answer 21

我在 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 output
AB    CD             Note
00    00             = AB
01    01             = AB
10    01             = AB - (A >> 1) & 0x1
11    10             = AB - (A >> 1) & 0x1

因此，如果我取上面的第一列 (A)，将其右移 1 位，然后从 AB 中减去它，我得到输出 (CD)。对 3 位的扩展类似；如果您愿意，可以使用上面我的 8 行布尔表来检查它。

• 唐·吉利斯

Answer 22

如果您使用 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 )

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

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

Answer 23

你能做的是

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

这背后的逻辑是 n-1 的位从 n 的最右边设置位反转。如果 n=6 即 110 那么 5 是 101 这些位从 n 的最右边设置位反转。因此，如果我们和这两个我们将在每次迭代中将最右边的位设为 0，并且总是转到下一个最右边的设置位。因此，计算设置位。当每个位都设置时，最差的时间复杂度将是 O(logn)。

Answer 24

我特别喜欢财富文件中的这个例子：

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

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

Answer 25

Java JDK1.5

整数.bitCount(n);

其中 n 是要计算其 1 的数字。

还要检查，

Integer.highestOneBit(n);
Integer.lowestOneBit(n);
Integer.numberOfLeadingZeros(n);
Integer.numberOfTrailingZeros(n);

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

Answer 26

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

Answer 27

我发现使用 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];
}

Answer 28

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

#include <bits/stdc++.h>

using namespace std;

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

Answer 29

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.0g++-9 -std=c++2a仍然不支持它。

该提案说：

标题：<bit>

namespace std {

  // 25.5.6, counting
  template<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++ 中循环移位（旋转）操作的最佳实践

Answer 30

这是一个可移植模块 (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

Answer 31

有很多算法来计算设置的位数；但我认为最好的是更快的！您可以在此页面上查看详细信息：

Bit Twiddling Hacks

我建议这个：

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

unsigned int v; // count the number of bits set in v
unsigned 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。

Answer 32

32位还是不是？在阅读了“破解编码面试”第 4 版练习 5.5（第 5 章：位操作）后，我刚刚在 Java 中使用了这种方法。如果最低有效位是 1 increment 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 的解决方案更直观，无论它们有多快。这取决于您对“最佳算法”的定义。

Answer 33

天真的解决方案

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

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

Brian Kerningam 的算法

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

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

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

时间复杂度为 O(1)

int table[256]; /*here size of the table is take 256 because when all 8 bit are set 
                 its decimal representation is 256*/

void initialize() //holds the number of set bits from 0 to 255
{
  table[0]=0;
  for(int i=1;i<256;i++)
     table[i]=(i&1)+table[i>>1];
}

int countSet(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;
}

Answer 34

我个人使用这个：

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

Answer 35

蟒蛇解决方案：

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 相加总是将 n 中的最低有效 1 位翻转为 0，并且保持所有其他位相同。

Answer 36

这是迄今为止尚未提及的使用位域的解决方案。以下程序使用 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(). 基于查找表的实现仍然要快一些，特别是对于 65 kB 的表。

Answer 37

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

迭代的“计数”运行时间与总位数成正比。它只是循环遍历所有位，由于 while 条件而稍早终止。有用，如果 1'S 或设置的位是稀疏的并且在最低有效位之间。

Answer 38

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

Answer 39

如果您使用支持 BMI2 的 CPU，则另一种 Hamming 权重算法

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

玩得开心！

Answer 40

在 Java 8 或 9 中，只需调用Integer.bitCount.

Answer 41

您可以使用名为 __builtin_popcount() 的内置函数。C++ 中没有 __builtin_popcount，但它是 GCC 编译器的内置函数。此函数以整数形式返回设置的位数。

int __builtin_popcount (unsigned int x);

参考：Bit Twiddling Hacks

Answer 42

从 Python 3.10 开始，您将可以使用该int.bit_count()函数，但暂时您可以自己定义该函数。

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

Answer 43

一种简单的方法，它可以很好地处理少量的位，就像这样（在这个例子中是 4 位）：

(i & 1) + (i & 2)/2 + (i & 4)/4 + (i & 8)/8

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

Answer 44

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

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

Answer 45

这是在 PHP 中工作的东西（所有 PHP 整数都是 32 位签名的，因此是 31 位）：

function bits_population($nInteger)
{

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

Answer 46

#!/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

Answer 47

如何将整数转换为二进制字符串并计数？

php解决方案：

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

Answer 48

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

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

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

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

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

Answer 49

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

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

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

Answer 50

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

Answer 51

我很失望地看到没有人对功能性主竞赛递归解决方案做出回应，这是迄今为止最纯粹的解决方案（并且可以与任何位长度一起使用！）：

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

Answer 52

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

cardinality()：返回此 BitSet 中设置为 true 的位数。

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

Answer 53

提供另一种未提及的算法，称为 Parallel，取自此处。很好的一点是它是通用的，这意味着位大小为 8、16、32、64、128 的代码是相同的。

我检查了 2^26 位大小为 8、16、32、64 的数量的值和时间的正确性。请参阅下面的时间。

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

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

#include <type_traits>
#include <cstdint>

template <typename IntT>
inline size_t PopCntParallel(IntT n) {
    // https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
    using T = std::make_unsigned_t<IntT>;
    #define MY_CHAR_BIT 8
    T v = T(n);
    v = v - ((v >> 1) & (T)~(T)0/3);                           // temp
    v = (v & (T)~(T)0/15*3) + ((v >> 2) & (T)~(T)0/15*3);      // temp
    v = (v + (v >> 4)) & (T)~(T)0/255*15;                      // temp
    return size_t((T)(v * ((T)~(T)0/255)) >> (sizeof(T) - 1) * MY_CHAR_BIT); // count
    #undef MY_CHAR_BIT
}

以下是我比较的两种算法。一种是带循环的 Kernighan 简单方法，取自此处。

template <typename IntT>
inline size_t PopCntKernighan(IntT n) {
    // http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan
    using 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 set
    return c;
}

另一种是使用 built-in // __popcnt16()MSVC的内在函数（doc here），这个内在函数应该提供非常优化的版本，可能是硬件：__popcnt()__popcnt64()

template <typename IntT>
inline size_t PopCntMsvcIntrinsic(IntT n) {
    // https://docs.microsoft.com/en-us/cpp/intrinsics/popcnt16-popcnt-popcnt64?view=msvc-160
    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 __popcnt(uint32_t(v));
    else
        return __popcnt64(uint64_t(v));
}

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

08 bit MsvcIntrinsic 4.8 ns
08 bit Parallel 4.0 ns
08 bit Kernighan 18.1 ns
16 bit MsvcIntrinsic 0.7 ns
16 bit Parallel 0.7 ns
16 bit Kernighan 25.7 ns
32 bit MsvcIntrinsic 1.6 ns
32 bit Parallel 1.6 ns
32 bit Kernighan 31.2 ns
64 bit MsvcIntrinsic 2.5 ns
64 bit Parallel 2.4 ns
64 bit Kernighan 49.5 ns

正如人们所看到的，提供的并行算法（3 个中的第一个）与 MSVC 的内在算法一样好，并且对于 8 位它甚至更快。

Answer 54

Kotlin 1.4 之前

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

这或多或少是这里看到的答案的副本https://stackoverflow.com/a/109025/6499953

使用 java 修复，然后使用 Intellij IDEA 社区版中的转换器进行转换

1.4 及更高版本（截至 21 年 5 月 5 日，未来可能会发生变化）

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

在它使用的引擎盖下，Integer.bitCount如此处所示

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

Answer 55

对于那些希望将C++11任何无符号整数类型用作 consexpr 函数的人（https://github.com/andry81/tacklelib/blob/trunk/include/tacklelib/utility/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)
        {
            return
                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)))))) + 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);
}

加上谷歌测试库中的测试：

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

Answer 56

以二进制表示（ 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 ）

你可以在这里运行代码

Answer 57

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

Answer 58

您可以执行以下操作：

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

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

工作可以解释如下：

首先，所有偶数位向右移动并与奇数位相加以计算两组中的位数。然后我们两人一组，然后四人一组，以此类推..

Answer 59

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

  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)
    */
    }

Answer 60

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

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

Answer 61

这是golang中的实现

func CountBitSet(n int) int {


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

    }
    return count
}

Answer 62

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

Answer 63

这也可以正常工作：

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