C++如何实现高效的位计数（Population Count）-C++-PHP中文网

不能直接用 std::popcount，因其依赖c++20、特定编译选项、无符号类型及较新编译器；__builtin_popcount需注意类型匹配与字长差异；查表法256字节最优；avx2仅适合大批量对齐数据。

c++如何实现高效的位计数（population count）

为什么不能直接用 `std::popcount` 就完事？

因为编译器支持和硬件指令依赖太强。C++20 引入了 std::popcount，但它要求编译器启用 -march=native 或明确目标架构（如 -march=haswell），且仅对无符号整数类型有效；对 int 直接传入会编译失败——std::popcount 不接受有符号类型，必须先转成 unsigned int 或 uint32_t。更麻烦的是，MSVC 2022 17.5+ 才开始部分支持，GCC 11+ 和 Clang 14+ 行为也不完全一致。

`__builtin_popcount` 在 GCC/Clang 下怎么安全用？

这是最常用也最稳妥的 fallback 方案，但要注意三类陷阱：

参数必须是 unsigned int：传 int x = -1; 进去会得到 32（补码解释），但语义上你可能想要绝对值的位数——得自己做 (unsigned int)x 显式转换
跨字长不通用：__builtin_popcount 只处理 32 位，__builtin_popcountll 处理 64 位，__builtin_popcountl 对应 unsigned long（在 Windows 上是 32 位，在 Linux x86_64 是 64 位）
没有 SFINAE 友好性：不能直接用于模板推导，比如 auto count = std::popcount(T{}); 在没 C++20 的项目里会硬报错，不如封装一层

推荐写个兼容封装：

template<typename t>
constexpr int popcount(T x) noexcept {
    if constexpr (std::is_same_v<t unsigned int>)
        return __builtin_popcount(x);
    else if constexpr (std::is_same_v<t unsigned long>)
        return __builtin_popcountl(x);
    else if constexpr (std::is_same_v<t unsigned long>)
        return __builtin_popcountll(x);
    else
        return std::popcount(static_cast<:make_unsigned_t>>(x));
}</:make_unsigned_t></t></t></t></typename>

手动实现查表法时，256 字节表够不够用？

够，而且是最平衡的选择。有人觉得“16-bit 表 64KB 太大”，其实没必要——现代 CPU L1 缓存普遍 32–64KB，256 字节能常驻缓存行，随机访问延迟极低。关键在于别写错索引逻辑：

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

对 uint32_t，别用 (x & 0xFF) + ((x >> 8) & 0xFF) + ...——这是加法，不是查表；正确是 pop8[x & 0xFF] + pop8[(x >> 8) & 0xFF] + pop8[(x >> 16) & 0xFF] + pop8[x >> 24]
查表数组必须声明为 static constexpr，否则每次调用都构造，GCC 可能不内联
如果目标平台内存极度受限（如嵌入式 ROM while (x) { x &= x - 1; count++; }，但最坏情况要循环 32 次，远不如查表稳定