位运算统计二进制中1的个数有四种主流方法：①按位与+右移（O(log n)）；②n&(n−1)清除最右1（循环次数=1的个数）；③固定位宽遍历（如32次，无分支）；④查表法或分治法（常数时间，适合高频场景）。

直接用位运算统计一个整数二进制中 1 的个数，核心是避开除法和取模，利用硬件级的 & 和 >>（或 & 和 n & (n−1)）快速定位、清除或检测比特位。效率高、代码短、不依赖标准库，特别适合嵌入式、算法竞赛和底层优化场景。

按位与 + 右移：逐位扫描最直观

每次用 n & 1 检查最低位是否为 1，再用 n >>= 1 把下一位“推”到最低位。循环直到 n 变成 0。

• 适合理解原理，逻辑清晰，兼容所有整数类型
• 注意：对有符号负数右移时，多数编译器做算术右移（高位补符号位），可能导致死循环；建议统一转为无符号类型处理，如 unsigned int u = (unsigned int)n
• 循环次数等于该数二进制总位数（例如 32 位 int 最多 32 次），时间复杂度 O(log n)

n & (n − 1)：每次清除一个 1，更省步数

利用关键性质：n & (n − 1) 能把 n 的二进制表示中最右边的 1 变成 0，其余位不变。每执行一次，就减少一个 1，计数加一，直到 n 为 0。

• 循环次数 = 二进制中 1 的实际个数（比如 12（1100）只循环 2 次）
• 天然规避负数右移问题，因为全程不依赖移位，只做减法和与运算
• 在稀疏数据（如掩码、标志位组合）中优势明显，平均比逐位扫描快得多

固定位宽遍历：适用于已知类型长度的场景

例如 int 是 32 位，可直接循环 32 次，用 (n >> i) & 1 判断第 i 位是否为 1。i 从 0 到 31。

• 无需判断 n 是否为 0，避免分支预测失败，利于 CPU 流水线执行
• 支持负数：因为不改变原值，也不依赖右移行为，而是用偏移后与 1 判断
• 适合编译器向量化或手动展开（如 unroll 8 次），在固定长度批量处理时吞吐更高

进阶技巧：查表法与分治并行统计

对性能极致要求的场景（如图像处理、密码学），可用预计算查表或位并行算法：

• 查表法：建一个 256 字节的数组 table[256]，存 0~255 每个数的 1 的个数；把 int 拆成 4 个字节，查表累加，仅需 4 次内存访问 + 3 次加法
• 分治法（JDK Integer.bitCount 原理）：用掩码和移位，两两一组统计 1 的个数，再四四合并、八八合并……最终在常数时间内完成，共 5 步位运算，无分支无循环
• 这些方法牺牲少量空间换速度，适合高频调用或大数据量批量统计