__builtin_popcount通常是最佳选择，因其直接编译为CPU原生popcnt指令，延迟低、吞吐高，且编译器自动降级兼容老CPU；需配-mpopcnt并传入无符号类型。
为什么 __builtin_popcount 通常是最佳选择
在 GCC/Clang 下，直接用 __builtin_popcount（对 unsigned int）或 __builtin_popcountll（对 unsigned long long）就能获得当前平台最优的 popcount 实现——它会自动编译为 CPU 原生指令（如 x86 的 popcnt），单条指令完成，延迟低、吞吐高。
常见误区是手动写查表法或 Brian Kernighan 算法以为更“可控”，但现代编译器对 builtin 的优化极其成熟，且能随目标架构自动降级（比如在不支持 popcnt 的老 CPU 上，GCC 会生成高效回退代码）。
- 必须加编译选项
-mpopcnt才能启用 x86 的popcnt指令；否则即使写了__builtin_popcount，GCC 也可能回退到软件实现 - 注意符号类型：传入负数（如
int）会导致未定义行为；务必转换为无符号类型再调用 - MSVC 用户请改用
__popcnt或__popcnt64（需包含<intrin.h></intrin.h>），它们不是 builtin，而是直接对应内在函数
手写查表法只在特定场景有用
当无法依赖编译器 builtin（例如嵌入式裸机、交叉编译链不支持），或需要确定性行为（如测试向量验证），才考虑手写。此时 256 元素的字节查表仍是实用底线。
典型错误是做成 65536 元素的 uint16_t 表——浪费缓存行，且现代 CPU 的 L1d 缓存带宽远不如寄存器+ALU 运算快；而 256 字节表可常驻 L1d，配合移位+掩码拆字节，实测比 64k 表更快。
立即学习“C++免费学习笔记（深入）”；
- 查表前先做
static const uint8_t popcount_table[256]，确保编译期初始化 - 对 64 位整数，避免循环 8 次：用
uint64_t x→(x & 0xFF) + ((x >> 8) & 0xFF) + ...展开更易被向量化；或者用_mm_movemask_epi8（SSE4.2）加速，但需额外指令集支持 - 不要对每个字节做分支判断（如 if-else 分高低位），查表本身已是 O(1)，分支反而引入预测失败惩罚
Brian Kernighan 算法适合稀疏位场景
当输入中“1”的数量极少（比如位掩码里通常只有几个 flag 被置位），n &= n - 1 循环的迭代次数等于 popcount 结果，实际比遍历所有位更快。
但它依赖分支预测，且每次迭代至少含一次减法、与运算和条件跳转，在密集位（如全 1）下性能断崖式下跌——此时它比查表慢 5–10 倍。
- 代码简洁：
int popcount(int n) { int c = 0; while (n) { n &= n - 1; ++c; } return c; } - 仅适用于整型，且对
0输入立即退出，无需特判 - 注意：
n必须是无符号类型，否则n - 1在n == 0时是大正数，循环不终止（有符号溢出未定义）
AVX512/VPOPCNTDQ 指令能批量处理但门槛高
如果你真在处理成千上万个 32/64 位整数（比如 bitmap 压缩、图算法中的邻接位集），AVX512 的 vpopcntd/vpopcntq 可单指令吞吐 16 个 int32_t 或 8 个 int64_t，理论吞吐翻倍。
但代价明显：仅限 Intel Ice Lake+/AMD Zen4+，需显式启用 -mavx512vl -mavx512bw -mavx512vpopcntdq，且数据要对齐到 64 字节；稍有不慎就触发 #UD 异常或 silently fallback 到标量。
- 别直接手写内联汇编——用
__builtin_ia32_vpopcntd_512等 GCC 内在函数，让编译器管寄存器分配和指令调度 - 小批量（
- 确认运行时 CPU 支持：用
__builtin_ia32_cpu_supports("avx512vpopcntdq")动态分发，别硬编码
真正关键的不是选哪个算法，而是明确你的数据分布、目标平台和性能瓶颈点。builtin 覆盖 95% 场景；查表和 Kernighan 是 fallback 安全网；AVX512 是少数人需要拧紧的那颗螺丝——但拧之前，先确认螺纹规格对得上。
