1. 题目拆解与学习价值位1的个数这道题算法圈里一般叫 Popcount 或 Hamming Weight讲人话就是给你一个非负整数你数一数它的二进制表示里有多少个 1。比方说数字 11二进制是 1011那答案就是 3。这题在很多面试题单里被归类为简单但我要泼一盆冷水能把这道题写出最优解的人其实并没有那么多。最常见的写法是循环 32 次逐个检查这当然对但如果你能写出 Brian Kernighan 算法的版本或者更进一步能画出分治并行计数的那个经典位运算魔法那面试官对你的印象绝对不一样。先说说我为什么觉得这道题值得拿出来单讲一天。日常工作里位运算用得不算频繁但一旦用到就是性能敏感的地方。比如网络数据包里统计标志位、图像处理里计算二值化图像的像素数量、海量 ID 去重时用 bitset 做布隆过滤器的容量估算底层都离不开 popcount。还有数据库里索引位图的计算、Redis 的 bitcount 命令本质都是这道题的工业级实现。你在 LeetCode 上把它 AC 了只觉得是刷了一题但在真实系统里这就是很多基础组件性能的基础。所以今天这篇不只是给一道题的题解我更想借这个题目把位运算的几个经典套路串一遍暴力法、Kernighan 优化、查表法、分治并行法再到语言内置实现。最终你会发现同一个需求在不同约束条件下解法可以差出几个数量级。这才是算法题真正有意思的地方。题目的输入输出也值得注意。在 LeetCode 的经典版本里输入是一个无符号整数在 Java 里是 int在 C/C 里看你用什么 API输出是 1 的个数。但不同语言对无符号的处理不一样这本身就是第一个坑后面我会专门讲到。现在按惯例先把这个题的本质看清楚二进制、位权、1 的分布这三个东西搞明白后面所有解法都是围绕它们转。2. 最直观的两种入门解法2.1 逐位检测从最低位开始查先写一个最没有技巧含量的版本。把整数想象成一排开关我们一个个拨过去看哪个是开的。每次检查最低位是不是 1然后右移一位直到数字变成 0。C 语言写法如下int hammingWeight(uint32_t n) { int count 0; while (n) { count n 1; n 1; } return count; }这里n 1是在做掩码操作与 1 做按位与只有最低位保留其他位全部清零。如果最低位是 1结果是 1count就加一如果是 0结果就是 0什么都不加。然后n 1把整个数字右移一位相当于扔掉已经检查过的最低位。这个解法的时间复杂度是 O(log n)更准确地说是 O(二进制位数)。对于 LeetCode 的测试数据最坏情况循环 32 次Java 的 int或者 64 次C 的 uint64_t常数很小实际跑起来并不慢。Python 版本也一起给出来def hammingWeight(n: int) - int: count 0 while n: count n 1 n 1 return countPython 的整数是任意精度的所以你不需要关心中间右移会不会溢出这个特性在后面某些解法里是个大坑Python 反而自动帮你绕开了。2.2 只数 1 的优化Brian Kernighan 算法逐位检测的写法循环次数取决于整数的二进制位长而不是 1 的个数。如果数字是 0x80000000也就是最高位是 1、其他位全是 0它要循环 32 次才能得出答案 1。这显然有点憨。Brian Kernighan 算法的核心思想就一句话n (n - 1)这个操作能把 n 的最低位的那个 1 变成 0。注意是最低位的 1不是最低位。举例来说n 12二进制 1100。n - 1 1011两者按位与结果是 1000等于 8。12 的最低位的 1 在第三位从低往高数这个操作精确地把它抹掉了。于是循环次数就变成了1 的个数int hammingWeight(uint32_t n) { int count 0; while (n) { n n - 1; count; } return count; }每次循环消灭一个 1循环次数等于答案本身。对于稀疏的二进制数这个解法快到飞起。最坏情况下比如 0xFFFFFFFF32 个 1循环 32 次和暴力法没有区别但平均下来明显更优。为什么n (n-1)能做到这件事你可以这样理解当 n 减 1 的时候最低位的那个 1 右边的所有位都变成 1而这个 1 本身变成 0。比如 1100 减 1因为第二位和第一位从低往高都是 0需要向第三位借位结果第三位变 0第二位和第一位变 1得到 1011。再把原来的 n 和它按位与那三个变化过的位里第三位本来是 1 现在变成 0 了右边两位本来就是 0与完之后依然是 0。于是恰好消掉了最低位的那个 1其他位纹丝不动。平时写业务代码如果你需要统计一个整数的二进制里 1 的个数而又不想引入复杂的查表逻辑这个解法是我最推荐背下来的。代码短逻辑直观效率也够好。n (n-1)本身还是一个高频考点它还能用来判断一个数是不是 2 的幂n 0 (n (n-1)) 0因为 2 的幂的二进制只有一个 1一次操作就变成 0 了。这属于买一赠一的收获。3. 查表法用空间换时间的经典思路前两种解法都是每调用一次就现场数一遍。但如果你的程序要频繁地调用 popcount比如在一个循环里对成千上万个整数做统计那每次都在那里移位、与运算累积起来就不是小开销了。这时候就该请出查表法。查表法的思路非常朴素既然计算慢那我提前把结果存起来用的时候直接取。好比你去菜市场买菜每种菜的价格你不可能每次现问心里有一本账直接付款。具体做法是先把 0 到 2558 位所有数字的 1 的个数算好存进一个长度为 256 的数组。然后统计一个 32 位整数时把它拆成 4 个 8 位的段每段直接查表加起来就行。static int popcount_table[256]; void init_table() { for (int i 0; i 256; i) { // 对8位数逐位统计也可以直接用__builtin_popcount popcount_table[i] (i 1) popcount_table[i 1]; } } int hammingWeight(uint32_t n) { return popcount_table[n 0xFF] popcount_table[(n 8) 0xFF] popcount_table[(n 16) 0xFF] popcount_table[(n 24) 0xFF]; }这里的动态规划递推式popcount_table[i] (i 1) popcount_table[i 1]本身也是一道小题i 的 1 的个数等于最低位加上去掉最低位后剩下部分的 1 的个数。这个思路叫递推打表比手动枚举 256 个值理性得多。查表法的查询部分是 O(1)四次数组访问加三次加法没有任何循环。代价是 256 个字节的内存。如果把表扩大到 16 位也就是 65536 个元素那 32 位整数只需要查两次表。内存变成 64KB换来的是更快的速度。这个权衡在嵌入式领域尤其重要如果你的单片机内存只有 4KB256 的表还行65536 的表就直接撑爆了。但如果你的程序跑在服务器上64KB 连 L1 Cache 都占不满查表速度会非常可观。Python 里也可以这么干只是 Python 的解释器开销比较大查表省下的那点时间可能被列表索引的 Python 层开销抵消所以 Python 里我更推荐直接用内置的int.bit_count()这个后面会细说。查表法真正的主场是 C、C、Rust 这类编译型语言或者 Java 这种 JIT 之后数组访问极快的环境。一个工程上的小细节init_table()一定别忘了在程序启动时调用否则表里全是 0查出来的结果全错。我见过不止一次线上事故就是因为某个基础库的初始化函数被条件编译宏给过滤掉了。初始化之后可以加一个断言比如assert(popcount_table[7] 3)防止表没建对。4. 分治并行计数位运算的魔法时刻如果说前面几种解法还在正常人的认知范围内那这一节的方法第一次看到的人大概率会懵一会儿。它不用循环、不查表、不递归只用几条位运算就把 32 位整数的 1 的个数算出来了。这就是经典的 SWARSIMD Within A Register寄存器内单指令多数据技巧也叫分治计数法。我先把这个写法的最终形态贴出来再拆开讲。以 32 位整数为例int hammingWeight(uint32_t n) { n (n 0x55555555) ((n 1) 0x55555555); n (n 0x33333333) ((n 2) 0x33333333); n (n 0x0F0F0F0F) ((n 4) 0x0F0F0F0F); n (n 0x00FF00FF) ((n 8) 0x00FF00FF); n (n 0x0000FFFF) ((n 16) 0x0000FFFF); return n; }第一眼看过去一堆魔法数字0x55555555、0x33333333、0x0F0F0F0F……这些不是随便写的它们分别是二进制下 0101、0011、00001111 重复填满 32 位的结果。理解了这个整个算法就通了。核心思想是分治求和先把相邻的 2 个 bit 合并成一组算出每组里 1 的个数再把相邻的 2 组4 个 bit合并算出每 4 个 bit 里 1 的个数然后 8 个 bit 一组、16 个 bit 一组最后 32 个 bit 全合并答案就出来了。第一步n 0x55555555取出所有奇数位的值(n 1) 0x55555555取出所有偶数位的值两者相加。因为 0x55555555 的二进制是 0101...0101与操作后奇数位保留偶数位清零。右移一位再与操作偶数位跑到奇数位的位置上再清零原本的偶数位。两个部分相加得到的结果里每 2 个 bit 一组存的正是这一组里 1 的个数。举例原来的 bit 对是 10奇数位是 1偶数位是 0相加得 01表示这一组有 1 个 1。原来的 bit 对是 11相加得 10表示有 2 个 1。这一步之后数据从原始二进制变成了每 2 位一个计数单元。第二步n 0x33333333取出每 4 位中的低 2 位(n 2) 0x33333333取出每 4 位中的高 2 位相加。因为此时每 2 位已经是计数单元值最大为 2二进制 10两个相加最大为 4二进制 100刚好能存进 4 位里不溢出。这一步之后每 4 位一组存的是这一组里 1 的个数。后面依次类推。第三步每 8 位一组第四步每 16 位一组第五步合并成 32 位的完整答案。每一步的掩码都保证相加结果不会溢出到下一组这是整个算法成立的关键。如果你要处理 64 位整数只需在最后加一步n (n 0x0000FFFF0000FFFF) ((n 32) 0x0000FFFF0000FFFF)前面的步骤的掩码也要相应地扩展成 64 位版本。原理完全一样。这个算法的精妙之处在于它利用了 CPU 的位级并行一条加法指令同时处理 16 组相互独立的子问题。所有步骤都是常数条指令没有分支没有跳转流水线不会被冲刷。对于那些数 1操作在热循环里的性能敏感场景手写 SWAR 至今仍有意义。我最初学这个方法的时候总觉得它像魔术。后来我换了个角度想这不就是归并排序的合并思想吗先解决小问题再把小问题的解两两合并成大问题的解。只是这里合并的载体是位运算而且所有子问题在同一时刻并行完成。算法之美往往就在这种跨界类比里。5. 语言内置实现与工程选型如果你的项目里真的需要统计 1 的个数我的建议是优先用语言内置函数不要自己造轮子。现代编译器对 popcount 的支持已经非常成熟。C/C 里GCC 和 Clang 都提供了内置函数__builtin_popcount和__builtin_popcountll分别处理 32 位和 64 位整数。在 x86 架构上如果编译器开启了-mpopcnt或-marchnative等它会直接编译成 CPU 的POPCNT指令如果 CPU 不支持编译器会自动生成一个优化的调用序列。这个函数属于编译器内置不需要引入任何头文件写起来非常方便。#include cstdint int hammingWeight(uint32_t n) { return __builtin_popcount(n); }C 20 标准库则提供了更规范的std::popcount定义在bit头文件里。它不依赖特定编译器的扩展跨平台性更好。推荐新代码直接用这个。Java 里Integer.bitCount(int)是标准库方法内部实现就是 SWAR 算法的 Java 版本。代码看多了你会发现Java 的官方实现和我上面贴的 C 版本几乎一模一样。Android 开发里Integer.bitCount在 ART 虚拟机下会被编译成 ARM 的VCNT指令或 x86 的POPCNT性能相当好。Python 3.10 开始int类型有了bit_count()方法之前只能自己写或者用bin(n).count(1)。bit_count()直接用底层的 C 实现对任意大整数都能快速统计。Go 语言在math/bits包里有bits.OnesCount系列函数实现对不同位宽做了优化部分架构上直接调用 CPU 指令。Rust 有u32::count_ones()等固有方法底层也会调用 LLVM 的ctpop内建同样可以编译成POPCNT。我把这些整理成一个表格供你参考语言推荐写法底层优化C / C (GCC/Clang)__builtin_popcount可映射 POPCNT 指令C20std::popcount标准库封装跨平台JavaInteger.bitCount手写 SWAR 后 JIT 优化Python 3.10int.bit_count()C 实现任意精度Gomath/bits.OnesCount各架构优化实现Rustcount_ones()LLVM ctop 内建工程选型的一条原则先测再换。拿 LeetCode 刷题时内置函数和手写版本差别不大但在生产环境大规模调用时建议用自带基准测试工具测一把看看内置版本在你的数据分布下是否真的更快。内置方案无论如何都比手写的版本更容易维护代码也短而且编译器的维护者早就帮你想好了各种边界情况。6. 常见问题与实战踩坑记录这道题虽然看起来简单但我辅导过不少同学也看过不少线上代码真正踩过的坑五花八门。整理几个典型问题每个我都标注了正确的处理方式这些比题解本身更值钱。6.1 有符号数右移的算术移位陷阱第一个坑藏在无符号三个字里。LeetCode 原题说的是 unsigned integer但很多人在 Java 里用的是int在 C 里用的是int。这就出事了。C 语言里int是有符号类型右移运算符对于有符号负数是算术右移也就是说最高位补的是符号位不是 0。如果n是负数n 1会把符号位一直往右带结果n永远不为 0你的循环就死循环了。就算侥幸不变成 0统计出来的数也完全不对。正确做法是C 语言用uint32_t或者unsigned intJava 里虽然int是有符号的但是算术右移、才是逻辑右移所以循环移位必须用或者直接用Integer.bitCount()让标准库帮你处理。Python 里没有这个问题因为 Python 的整数右移永远是逻辑右移而且无限精度不会有符号扩展的困扰。6.2 表未初始化导致的结果全错查表法里忘记调用初始化函数是第二大坑。特别是当你把查表逻辑封装成一个静态库发给别人用时使用者根本不知道还有一个初始化步骤。更隐蔽的是初始化函数加了一个断言的保护程序崩溃了使用者跑过来问你接口是不是有问题你在那儿排查了半天最后发现是初始化没调用。解决方案是不要把初始化函数暴露给外部用 C 的静态初始化或者 C 的函数内静态局部变量static局部变量在首次使用时初始化线程安全或者直接用常量表。所谓常量表就是提前用脚本生成 256 个数字的数组写死在代码里不要运行时计算。这样根本不存在忘了初始化的问题。6.3 查表法与循环混用导致的性能误解有人为了省事在需要统计的循环内部每次都调用一个查表函数。如果这个查表函数本身的逻辑很简单没问题但如果函数内部还做了边界检查、表指针判空之类的操作这些分支会污染 CPU 的分支预测性能反而比直接写循环还差。这一点在 C/C 里尤其明显所以内联inline或者宏展开是查表法常用的工程手段。你还可以考虑一次处理多个整数比如把 8 个整数各自查表的结果用 SIMD 向量化累加这个优化空间非常大适合追求极致性能的场景。6.4 忽视了n (n-1)会修改原值的问题Kernighan 算法的循环体n n - 1会直接修改传入的参数。如果你在函数外部还需要用到原始值记得先拷贝一份。虽然这个提醒看起来废话但我真见过有人把参数按引用传进来统计完 1 的个数原数字也变成 0 了后面代码用它判断奇偶性直接崩了。排查了很久才发现是这里的问题。6.5 边界值测试清单不管你用哪种解法提交之前至少把下面几组边界值测一遍0结果为 01结果为 1对应二进制只有一个 10x7FFFFFFFJava 的 int 最大值31 个 1结果为 310xFFFFFFFF32 个 1结果为 32。注意在 Java 里 0xFFFFFFFF 是 -1不能用 int 直接表示需要写成 0xFFFFFFFFL 再转或者干脆用Integer.bitCount(-1)来测结果为 320x80000000只有最高位是 1结果为 1一张表格总结排查要点问题现象可能原因解决办法循环死循环有符号数算术右移用 uint32_t 或查表全返回 0表未初始化用常量表或静态初始化大数输入结果不对未处理 64 位整数用 popcountll 或扩展 SWAR原值被修改Kernighan 中 n 被改写传入前先拷贝6.6 关于算法复杂度的复盘暴力法是 O(k)k 是二进制位数Kernighan 是 O(m)m 是 1 的个数查表法是 O(1)SWAR 是 O(1) 但常数更小CPU 指令是 O(1) 且硬件级并行。这道题最好的地方在于它让你看到一个指标怎么一步步被优化到极致也让你明白优化的本质是利用问题的特性要么利用 1 的稀疏性要么利用 CPU 的并行能力。我个人在实际项目里的经验是如果你的代码路径里需要反复统计位 1 的个数而且这段代码确实是热点先用内置函数然后做 profiling确认开销占比真的够大再考虑手写 SWAR。不要为了炫技在业务代码里手写一堆魔法数字一个月后你自己都看不懂那一串 0x55555555 是干嘛的。如果一定要写务必配上注释解释每一行的意图。7. 从一道题延伸出去的思考刷题最忌讳的是背答案。位运算这个主题把一个 popcount 吃透你能顺带解决一堆看似无关的问题判断 2 的幂n 0 (n (n - 1)) 0这个刚才提过。统计两个整数二进制位不同的个数——汉明距离本质是popcount(a ^ b)先异或把不同位变成 1再数 1。只出现一次的数字系列用异或消除成对出现的数字。子集枚举时用 i 的二进制表示选择哪些元素。这些题全都指向同一个底层能力能不能把十进制抽象成二进制去看问题。还有一点如果你是在校学生或者准备面试我建议你把这个题目的五种解法全部手写一遍不查资料然后在心里过一遍每种解法的复杂度、适用场景、边界条件。能做到这一步你对位运算的基础就算打牢了。面试官问到这个题时你不光给他一个解还能告诉他为什么在嵌入式环境用查表、在服务器环境用内置函数、在算法竞赛里常写 Kernighan这体现的就是真实工程经验的积累比单纯 AC 的含金量高得多。最后分享一个我自己常用的记忆方法。0x55555555 这种魔法数字不要死记硬背这样写出来自己心里也发虚。我每次都是先写二进制0101、0011、00001111、0000000011111111然后心里拿 16 进制快速换算写多了自然就记住了。实在懒得换算也可以在代码里用宏定义写清楚含义例如#define MASK_2BIT 0x55555555可读性一下就上来了。今天这道位1的个数就聊到这里。从最简单的逐位检测到硬件指令我们几乎把位运算的所有经典套路都过了一遍。以后你再看到类似的位操作题心里就有底了。