位1的个数：从逐位检测到SWAR并行计数的优化全解

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，结果是 1，count就加一；如果是 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 count

Python 的整数是任意精度的，所以你不需要关心中间右移会不会溢出，这个特性在后面某些解法里是个大坑，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，循环次数等于答案本身。对于稀疏的二进制数，这个解法快到飞起。最坏情况下（比如 0xFFFFFFFF，32 个 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 到 255（8 位）所有数字的 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，换来的是更快的速度。这个权衡在嵌入式领域尤其重要：如果你的单片机内存只有 4KB，256 的表还行，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 的个数算出来了。这就是经典的 SWAR（SIMD 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（或-march=native等），它会直接编译成 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。

我把这些整理成一个表格供你参考：

工程选型的一条原则：先测再换。拿 LeetCode 刷题时，内置函数和手写版本差别不大；但在生产环境大规模调用时，建议用自带基准测试工具测一把，看看内置版本在你的数据分布下是否真的更快。内置方案无论如何都比手写的版本更容易维护，代码也短，而且编译器的维护者早就帮你想好了各种边界情况。

6. 常见问题与实战踩坑记录

这道题虽然看起来简单，但我辅导过不少同学，也看过不少线上代码，真正踩过的坑五花八门。整理几个典型问题，每个我都标注了正确的处理方式，这些比题解本身更值钱。

6.1 有符号数右移的算术移位陷阱

第一个坑藏在"无符号"三个字里。LeetCode 原题说的是 unsigned integer，但很多人在 Java 里用的是int，在 C 里用的是int。这就出事了。

C 语言里，int是有符号类型，右移运算符对于有符号负数是算术右移，也就是说，最高位补的是符号位，不是 0。如果n是负数，n >>= 1会把符号位一直往右带，结果n永远不为 0，你的循环就死循环了。就算侥幸不变成 0，统计出来的数也完全不对。

正确做法是：C 语言用uint32_t或者unsigned int；Java 里虽然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：结果为 0
• 1：结果为 1，对应二进制只有一个 1
• 0x7FFFFFFF（Java 的 int 最大值）：31 个 1，结果为 31
• 0xFFFFFFFF：32 个 1，结果为 32。注意在 Java 里 0xFFFFFFFF 是 -1，不能用 int 直接表示，需要写成 0xFFFFFFFFL 再转，或者干脆用Integer.bitCount(-1)来测，结果为 32
• 0x80000000：只有最高位是 1，结果为 1

一张表格总结排查要点：

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的个数"就聊到这里。从最简单的逐位检测到硬件指令，我们几乎把位运算的所有经典套路都过了一遍。以后你再看到类似的位操作题，心里就有底了。