c++oding="utf-8" ?>
__builtin_popcount通常是最优解，因其在现代x86/x64和arm平台直接编译为单周期硬件指令popcnt或cnt，远快于循环、查表等软件实现，且无分支、无缓存依赖。
为什么 __builtin_popcount 通常就是最优解
在绝大多数现代 x86/x64 和 ARM 平台的 GCC/Clang 下，__builtin_popcount（对 unsigned int）或 __builtin_popcountll（对 unsigned long long）会直接编译为硬件指令 popcnt（x86）或 cnt（ARM），单周期完成 64 位计数。它比任何纯 C++ 循环或查表都快，且无分支、无缓存依赖。
实操建议：
- 确认编译器支持：GCC ≥ 4.2、Clang ≥ 3.0 默认启用；MSVC 用
__popcnt（需#include <intrin.h></intrin.h>，且要检查 CPU 是否支持POPCNT指令集） - 确保开启编译优化（
-O2或更高），否则可能退化为软件实现 - 注意类型匹配：
__builtin_popcount只接受unsigned int；传入int负值会按补码解释，结果非预期
手写 portable 实现时，Brian Kernighan 算法最实用
当无法依赖编译器内置函数（如嵌入式环境、裸机开发、或需跨平台可移植性），n & (n - 1) 技巧是平衡简洁性与效率的首选——它只循环“1”的个数次，而非固定 32/64 次。
示例：
int popcount_bk(unsigned int n) {
int c = 0;
while (n) {
n &= n - 1; // 清除最低位的 1
c++;
}
return c;
}
常见错误现象：
- 用
n = n & (n - 1)但漏掉&，写成赋值=→ 无限循环 - 对有符号类型操作（如
int）且输入为负 → 行为未定义（C++20 前）或补码解释，易误判 - 未考虑 0 输入：该算法天然处理 0（循环不执行），无需特判
查表法在特定场景下仍有价值
查表法（如 8 位表 + 四次查表）在以下情况仍具优势：目标平台无 popcnt 指令（如老旧 ARMv7）、编译器未启用内置函数、或需极致确定性延迟（避免指令调度不确定性）。
实操要点：
- 用
static constexpr std::array<uint8_t></uint8_t>定义表，确保编译期初始化，避免运行时开销 - 避免用
std::vector或动态分配——破坏 cache locality - 对 64 位数，拆成 8 个 byte：
table[n & 0xFF] + table[(n >> 8) & 0xFF] + ...；注意移位和掩码顺序，别漏括号 - 性能陷阱：若数据局部性差（随机地址访问），L1 cache miss 开销可能反超计算本身
std::popcount（C++20）不是万能替代
std::popcount 是标准库提供的可移植接口，但它要求编译器实际实现为硬件指令才高效；否则可能退化为软件回退（如某些 libc++ 版本对 unsigned short 的实现仍用循环）。
使用前提：
- C++20 编译模式（
-std=c++20） - 传入类型必须是无符号整型（
unsigned char到unsigned long long），且不能是自定义整型别名（如using u32 = uint32_t在部分编译器上可能不触发特化） - Clang ≥ 12 / GCC ≥ 12 才对
std::popcount做了较完整的硬件指令映射；旧版本可能全程走模板回退
真正需要跨平台又不想赌编译器实现质量时，不如显式用 __builtin_popcount + fallback 宏封装，比盲目信赖 std::popcount 更可控。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
