位1的个数：从逐位扫描到SWAR，一文吃透二进制位运算核心技巧

今天这期“每天学习一点算法”想聊一个看起来特别不起眼、但值得仔细品位的题目——位1的个数。题目一句话就能说清楚给定一个无符号整数统计它的二进制表示里有多少个1。你可能会想这有什么好学的转成字符串数一遍不就行了。但真正动手的人会发现这道题背后藏着位运算里最经典的一整串技巧逐位扫描、消掉最低位1、查表、分组并行统计。从最朴素的写法到常数时间的极速实现它几乎串起了整条位运算学习路径。不管你是刚入门算法、准备面试还是工作多年想补一补底层基础这一篇都值得花十分钟读完。下面我把每个解法的原理、代码和踩坑点都摊开讲最后再聊聊工程里到底该用哪种。1. 题目交给我们的任务统计二进制里有多少个11.1 题干与几个直观例子“位1的个数”翻译成英文通常叫 Number of 1 Bits在信息论里有个更正式的名字叫汉明重量Hamming Weight。它要求输入一个无符号整数输出它的二进制表示中 1 的个数。这里有一个容易忽略的点题目说的是“按二进制位来看”所以哪怕某些语言里整数带符号我们统计的也只是位模式里的 1而不是正数还是负数。举几个例子就能立刻明白输入十进制十六进制二进制表示输出的 1 的个数110x0B101131280x8010000000100x00000xFFFFFFFF0xFFFFFFFF32 个 132也就是说输入 11二进制是 1011里面有 3 个 1答案就是 3输入 128二进制只有最高位是 1答案就是 1。这个定义非常朴素没有什么弯弯绕绕。1.2 为什么这道题值得单独写一篇说句实话我见过不少工作三五年的朋友第一反应居然是把整数转成二进制字符串再count(1)。能跑通但完全没接触到这道题想教给你的东西。位运算在很多面试和竞赛里属于“高频但基础”的板块而“位1的个数”是其中最温和的入门点。它好在哪好在解法梯度非常清晰先能用最直的逐位法再理解n (n-1)的借位技巧最后能讲清楚查表法和 SWAR 分组统计这四层正好对应了从“能写”到“真懂”到“见过世面”的完整过程。再加上汉明距离、布隆过滤器等工程场景都会用到它把它吃透的性价比非常高。2. 最直白的做法从最低位开始一位一位数2.1 取最低位为什么用 n 1先看一个最基础的事实任何整数和 1 做按位与结果只保留最低位。最低位是 1结果就是 1最低位是 0结果就是 0。因为x 1本质上把除了最低位以外的所有二进制位全部清零了。拿到最低位之后怎么办把数字右移一位原来的次低位就变成新的最低位再做一次n 1就能取到原来的次低位。如此循环就像从柜子最底层抽屉开始一层一层往上检查每检查完一个抽屉就把它关掉继续看上一层。32 位整数就循环 32 次8 位整数就循环 8 次。这个方法理解起来没有任何障碍是后面所有优化方案的起点。2.2 三种语言的最小实现Java 版本我特意用而不是这是很多人第一次写就容易踩的坑public int hammingWeight(int n) { int ans 0; for (int i 0; i 32; i) { ans (n i) 1; } return ans; }是逻辑右移高位补 0是算术右移高位补符号位。题目按无符号视角处理所以逻辑右移更贴近题意。其实用在统计1时也不会出错因为我们每次只取最低位高位补什么都不影响这个值但如果你写成while(n ! 0)并搭配负数就会因为高位一直补 1 而陷入死循环。这就是 Java 有符号类型带来的坑。Python 版本可以写成def hamming_weight(n: int) - int: ans 0 for _ in range(32): ans n 1 n 1 return ansPython 的整数是无限精度的负数右移也是算术右移所以这个写法只对非负输入成立。题目如果约定输入是非负的 32 位整数那就没问题如果想处理任意非负大整数可以把循环次数改成n.bit_length()不过这是后话了。C 版本则清爽很多int hammingWeight(uint32_t n) { int ans 0; while (n) { ans n 1; n 1; } return ans; }为什么这里敢用while (n)因为uint32_t是无符号类型右移是逻辑右移n 最终一定会变成 0不会死循环。这也是一个典型的“类型决定行为”的例子。2.3 复杂度与实测感受固定循环 32 次的写法时间复杂度可以认为是常数级 O(1)但常数并不小每次都要做一次移位和一次与运算。C 里用while (n)的版本循环次数等于 n 的有效二进制位数最坏 32 次平均会少一些。实测上如果只算一两个数这种差异完全感知不到但如果跑一百万次甚至更多差别就会显现出来。不过逐位法最大的意义不是跑得快而是建立一条基线你知道最朴素的答案长什么样才能判断后续优化到底好在哪。先别跳步老老实实把这一版写通再谈优化。3. 核心进阶n (n - 1) 一次摘掉一个13.1 借位机制为什么 n-1 会把最右侧的1变成0这是整篇文章最重要的一节。记住一个结论对任意正整数 nn (n - 1)会把二进制表示里最右侧的那个 1 变成 0其他位保持不变。为什么因为减法会触发借位。看一个具体例子n 208它的二进制是11010000n - 1 207二进制是11001111两者按位与11010000 11001111 11000000观察这个过程n - 1找到最右侧的 1也就是从低位往上数遇到的第一个 1向它借位。这个 1 变成 0而它右边原本的 0 全部因为借位变成了 1。接着做按位与左边的位保持不变最右侧那个 1 以及它右边的位全部归零。用一句话说这个操作精准地“删掉”了二进制里的一个 1。那数 1 的个数就变得很简单了不断执行n n - 1每执行一次就删掉一个 1答案加 1直到 n 变成 0。循环次数不是固定 32 次而是恰好等于 1 的个数。3.2 代码与手动推演Python 版只要几行def hamming_weight(n: int) - int: ans 0 while n: n n - 1 ans 1 return ans手动推演一下 n 13二进制是1101第一轮1101 1100 1100计数 1第二轮1100 1011 1000计数 2第三轮1000 0111 0000计数 3返回 3。整个过程非常顺滑。n 0 时循环一次都不执行直接返回 0边界天然正确。这里有一个大家容易担心的点如果 n 是负数n - 1会不会因为符号位而出问题按位运算只看二进制位模式补码的减法和无符号减法在位级行为上完全一致所以n (n-1)对负数同样成立。Java 里你可以放心用它处理按无符号视角看待的 intPython 如果想模拟定长的 32 位无符号数可以先对 n 做一次n 0xFFFFFFFF来限制宽度。3.3 一个式子两种用法顺带判断 2 的幂这个式子不必只在数 1 的时候用。判断一个正整数是否是 2 的幂经典写法是def is_power_of_two(n: int) - bool: return n 0 and (n (n - 1)) 0原理就是2 的幂的二进制表示里恰好只有一个 1。执行一次n (n-1)应该直接变成 0。例如 8 是10008 7 0而 9 是10019 8 1000不为 0所以 9 不是 2 的幂。理解了这个式子相当于同时拿下了“数 1”和“判断 2 的幂”两个知识点这也是很多题解把它列为核心技巧的原因。3.4 什么时候别用这个技巧虽然n (n-1)很漂亮但它不是银弹。如果输入数据里 1 的个数很多循环次数接近 32并不比逐位法快多少如果统计吞吐量极大某些 CPU 上固定循环的逐位法反而因为分支预测和流水线友好而表现更好。真正生产环境里语言标准库往往早就提供了更极致的实现没必要手写。但作为学习它仍然是必须掌握的。因为它教给你的不只是“少写几行代码”而是“从二进制结构出发设计算法”的思维方式。这种思路比代码本身值钱得多后面看查表法和 SWAR 时你会更有体感。4. 再进一步查表法与 SWAR 分组统计4.1 查表法把答案提前算好当需要反复统计大量整数的 1 个数时查表法是最直白的优化思路既然 8 位以内的数字一共只有 256 种每一种的 1 个数都可以预先算好统计一个 32 位整数时把它切成 4 个 8 位段分别查表再加起来。Java 代码可以写成这样private static final int[] TABLE new int[256]; static { for (int i 1; i 256; i) { TABLE[i] (i 1) TABLE[i 1]; } } public int hammingWeight(int n) { int ans 0; for (int i 0; i 4; i) { ans TABLE[n 0xFF]; n 8; } return ans; }初始化表的递推逻辑很妙数字 i 的 1 个数等于它最低位i 1加上右移一位后的 1 个数。这个递推本身也是“位1个数”问题的一个微型解。实际工程里如果不想重复初始化可以用静态块只算一次或者直接把 256 个值硬编码成常量数组。查表法的时间复杂度同样是常数但循环只有 4 次通常比逐位法快不少。代价是要付出 256 字节左右的空间这在现代缓存敏感的代码里基本可以忽略。4.2 SWAR在寄存器里并行数查表法已经很快了但还有更接近底层的路线SWARSIMD Within A Register寄存器内并行。它的核心思路是不借助数组单靠移位、掩码和加法在同一个寄存器里把 32 位分成若干小组先让每组内部并行统计出 1 的个数再把小计逐层合并成大计。直接看代码这段值得每个学位运算的人都读一遍public static int popCount(int x) { // 每 2 位一组统计每组 1 的个数 x (x 0x55555555) ((x 1) 0x55555555); // 每 4 位一组合并相邻两个 2 位小组 x (x 0x33333333) ((x 2) 0x33333333); // 每 8 位一组合并相邻两个 4 位小计 x (x 0x0F0F0F0F) ((x 4) 0x0F0F0F0F); // 每 16 位一组 x (x 0x00FF00FF) ((x 8) 0x00FF00FF); // 最终合并成 32 位总计数 x (x 0x0000FFFF) (x 16); return x 0x3F; }逐步解释每一步在干什么第 1 步掩码0x55555555的二进制是0101...0101它负责取出每个 2 位小组的低位x 1之后再与同样的掩码取出的是每个 2 位小组的高位。两者相加后每个 2 位小组里存的就是原来这两位上 1 的个数。第 2 步掩码0x33333333是0011...0011把相邻两个 2 位小组合并成一个 4 位小组每个 4 位组里存着原来 4 位的 1 的总数。第 3 步到第 5 步每步把相邻小组合并一次从 4 位倒 8 位8 位倒 16 位最后合并成整个 32 位的总数。手动推演一个 8 位的例子x 10110110一共有 5 个 1第 1 步用 8 位掩码01010101推演结果按 2 位一组解释得到 1、2、1、1总和 5第 2 步用00110011合并成 4 位一组得到 3 和 2总和 5第 3 步用00001111合并成 8 位直接得到 5整个过程直观展示了“分组并行 逐层合并”。需要注意在 C 里应该用uint32_t保证右移是逻辑右移在 Java 里 int 即使有符号位运算结果最终也是 0 到 32 之间的数最后再 0x3F兜底即可。4.3 该不该背 SWAR直接说结论不需要背具体掩码但要理解思路。面试官如果追问“还能不能更快”你能说出查表法和 SWAR 两个方向就已经超过绝大多数候选人了。真正写生产代码时标准库会帮你完成这件事但看懂标准库的实现至少能让你在需要极致性能的时候不心虚。说得更直白一点SWAR 是“见识”n (n-1)是“手感”。前者让你不会被难倒后者让你写代码顺利。两样都有才算把这道题吃透。5. 落地工程能调库就调库但得知道它在干什么5.1 各语言的一行 API日常业务代码里我强烈建议直接用标准库不用自己造轮子。几个主流语言的写法如下语言推荐写法说明JavaInteger.bitCount(n)JDK 自带内部就是 SWAR 思路C / C__builtin_popcount(x)编译器内置函数可能直接映射到 CPU 硬件指令Python 3.10n.bit_count()官方新增方法老版本用bin(n).count(1)Gobits.OnesCount(uint(n))标准库math/bitsRustn.count_ones()内置方法直接可用为什么建议调库因为这些实现经过多年优化甚至会用上 CPU 的 POPCNT 一类专属指令。你手写一个逐位循环代码可能没问题但确实没有库快也没必要。5.2 真实场景汉明距离、布隆过滤器、校验“位1的个数”不是孤立的数学玩具它和工程结合得很紧密。汉明距离两个等长二进制串之间对应位不同的个数。计算方法就是两个数做异或然后统计结果里 1 的个数。这在纠错码、信息相似度计算里非常常见。布隆过滤器一个位数组里已经置为 1 的位数直接影响误判率。统计置位数这件事本质上就是在做“位1统计”。奇偶校验与校验和某些校验算法需要按位汇总状态位1统计也经常出现在其中。图像二值化后的面积估算、稀疏数据压缩等场景也会以各种改头换面的方式用到它。理解这些场景你就能明白为什么“每天学习一点算法”值得坚持——很多看似抽象的题目换个马甲就出现在现实工程中。5.3 我的刷题与面试建议按我自己的经验这道题可以分三个层次准备第一遍老老实实写逐位法确保能解释清楚1和右移的作用。第二遍写n (n-1)版本并且能讲出借位原理不是背代码。第三遍能口头描述查表法和 SWAR 的思路不用默写掩码但至少能画出分组合并的方向。面试时把n (n-1)作为主要解法来讲最后补一句“如果数据量很大还有查表法和 SWAR 的分组统计思路”这就非常完整。不要一上来就甩 SWAR容易显得像背答案先把原理讲清楚再展示延展知识面官观感会好很多。写到这儿我不禁想起这个系列的初衷。很多朋友问算法题要不要背我的答案一直是不要背解法要背思路。位1的个数就是一个典型——你只有亲手推过n-1的借位过程才会明白为什么一行n n-1就能消掉一个 1。如果你只记住一个口诀我希望是这句想数 1先借位。下次遇到任何需要统计二进制位的问题先画一张二进制展开图答案往往就藏在结构里。