代表数字 7 的 8 位看起来像这样：
00000111设置三位。
什么算法来确定 32 位整数中的设置位数？
这被称为 ' 汉明重量 '，'popcount'或' 侧向添加 '。
“最佳” 算法实际上取决于您使用的 CPU 以及您的使用模式。
一些 CPU 有一个内置指令来执行它，而另一些 CPU 具有作用于位向量的并行指令。并行指令（如 x86 的popcnt ，支持它的 CPU）几乎肯定会是最快的。一些其他架构可能具有使用微码环路实现的慢速指令，该循环每周期测试一点（ 需要引用 ）。
如果您的 CPU 具有大缓存和 / 或您在紧密循环中执行大量这些指令，则预先填充的表查找方法可以非常快。然而，由于 “高速缓存未命中” 的代价，它可能会受到影响，其中 CPU 必须从主存储器中获取一些表。
如果你知道你的字节大部分是 0 或大部分是 1，那么这些场景的算法非常有效。
我相信一个非常好的通用算法如下，称为 “并行” 或 “可变精度 SWAR 算法”。我用 C 语言伪语言表达了这一点，您可能需要调整它以适用于特定语言（例如，在 C ++ 中使用 uint32_t，在 Java 中使用 >>>）：
int numberOfSetBits(int i)
{
// Java: use >>> instead of >>
// C or C++: use uint32_t
i = i - ((i >> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}这具有所讨论的任何算法的最佳最坏情况行为，因此将有效地处理您抛出的任何使用模式或值。
这种按位 SWAR 算法可以在多个向量元素中同时进行并行化，而不是在单个整数寄存器中，以便在具有 SIMD 但没有可用的 popcount 指令的 CPU 上加速。 （例如 x86-64 代码必须在任何 CPU 上运行，而不仅仅是 Nehalem 或更高版本。）
但是，对 popcount 使用向量指令的最佳方法通常是使用变量 shuffle 在每个字节并行执行 4 位的表查找。 （4 位索引保存在向量寄存器中的 16 个条目表）。
在 Intel CPU 上，硬件 64 位 popcnt 指令可以胜过SSSE3 PSHUFB位并行实现大约 2 倍，但PSHUFB 是你的编译器恰到好处 。否则 SSE 可能会显着提前。较新的编译器版本了解Intel上的popcnt false 依赖性 问题 。
参考文献：
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）
还要考虑编译器的内置函数。
例如，在 GNU 编译器上，您可以使用：
int __builtin_popcount (unsigned int x);
int __builtin_popcountll (unsigned long long x);在最坏的情况下，编译器将生成对函数的调用。在最好的情况下，编译器将发出 cpu 指令以更快地完成相同的工作。
GCC 内在函数甚至可以跨多个平台工作。 Popcount 将成为 x86 架构的主流，因此现在开始使用内在函数是有意义的。其他架构多年来一直有很多人。
在 x86 上，您可以告诉编译器它可以使用-mpopcnt或-msse4.2来支持popcnt指令，以启用在同一代中添加的向量指令。请参阅GCC x86 选项 。 -march=nehalem （或-march=您希望代码假设和调整的 CPU）可能是一个不错的选择。在较旧的 CPU 上运行生成的二进制文件将导致非法指令错误。
要为您构建它们的机器优化二进制文件，请使用-march=native （使用 gcc，clang 或 ICC）。
MSVC 为 x86 popcnt指令提供了一个内在函数 ，但与 gcc 不同，它实际上是硬件指令的固有指令，需要硬件支持。
使用std::bitset<>::count()而不是内置
理论上，任何知道如何有效地为目标 CPU 进行 popcount 的编译器都应该通过 ISO C ++ std::bitset<>公开该功能。在实践中，对于某些目标 CPU，在某些情况下，您可能会更好地使用 bit-hack AND / shift / ADD。
对于硬件 popcount 是可选扩展（如 x86）的目标体系结构，并非所有编译器都有std::bitset在可用时利用它。例如，MSVC 无法在编译时启用popcnt支持，并且总是使用表查找 ，即使使用/Ox /arch:AVX （这意味着 SSE4.2，尽管从技术上讲， popcnt有一个单独的功能位。）
但至少你得到的东西在任何地方都可以使用，并且 gcc / clang 具有正确的目标选项，你可以获得支持它的架构的硬件 popcount。
#include <bitset>
#include <limits>
#include <type_traits>
template<typename T>
//static inline // static if you want to compile with -mpopcnt in one compilation unit but not others
typename std::enable_if<std::is_integral<T>::value, unsigned >::type
popcount(T x)
{
static_assert(std::numeric_limits<T>::radix == 2, "non-binary type");
// sizeof(x)*CHAR_BIT
constexpr int bitwidth = std::numeric_limits<T>::digits + std::numeric_limits<T>::is_signed;
// std::bitset constructor was only unsigned long before C++11. Beware if porting to C++03
static_assert(bitwidth <= std::numeric_limits<unsigned long long>::digits, "arg too wide for std::bitset() constructor");
typedef typename std::make_unsigned<T>::type UT; // probably not needed, bitset width chops after sign-extension
std::bitset<bitwidth> bs( static_cast<UT>(x) );
return bs.count();
}在 Godbolt 编译器资源管理器中查看来自 gcc，clang，icc 和 MSVC的 asm。
x86-64 gcc -O3 -std=gnu++11 -mpopcnt发出以下信息：
unsigned test_short(short a) { return popcount(a); }
movzx eax, di # note zero-extension, not sign-extension
popcnt rax, rax
ret
unsigned test_int(int a) { return popcount(a); }
mov eax, edi
popcnt rax, rax
ret
unsigned test_u64(unsigned long long a) { return popcount(a); }
xor eax, eax # gcc avoids false dependencies for Intel CPUs
popcnt rax, rdi
ret PowerPC64 gcc -O3 -std=gnu++11发出（对于int arg 版本）：
rldicl 3,3,0,32 # zero-extend from 32 to 64-bit
popcntd 3,3 # popcount
blr这个源根本不是 x86 特定的或 GNU 特定的，但只能通过 gcc / clang / icc 很好地编译 x86。
另请注意，gcc 对没有单指令 popcount 的体系结构的回退是一次一个字节的表查找。 例如，这对于 ARM来说并不是很好。
在我看来，“最佳” 解决方案是另一个程序员（或两年后的原始程序员）可以阅读而没有大量评论的解决方案。你可能想要一些已经提供的最快或最聪明的解决方案，但我更喜欢可读性而不是聪明。
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);
}虽然这些依赖于特定的数据类型大小，因此它们不具备可移植性。但是，由于许多性能优化无论如何都不可移植，这可能不是问题。如果你想要便携性，我会坚持使用可读的解决方案。