先聊一个特别容易被低估的题目。你刷算法题或者准备面试的时候只要打开“位运算”这个标签几乎一定会撞见“0和1的个数”。这题目听起来简单到不像话——不就是把一个整数转成二进制然后数一数里面有幾個0、幾個1嘛。但真正往深处聊你会发现它几乎涵盖了位运算里所有核心技巧逐位扫描、Brian Kernighan 消位、查表、分治掩码、内置指令甚至还能扯到数位DP和布隆过滤器。这篇文章就把这道题彻底拆开讲透。我会从题目本身的三种口径开始把统计1的个数五种主流方案全部实现一遍再讲清楚0的个数在不同场景下该怎么算最后结合汉明距离、bitmap、状压DP这些真实应用场景把容易踩的坑一个一个列出来。不管你是刚入门想抄一份能跑的代码还是老手想补一下底层原理这篇都值得花几分钟读到底。1. 先把问题定义清楚1.1 一道看似简单的算法题很多题目给出的题干是这个样子输入一个正整数 n返回它的二进制表示中 1 的个数。偶尔会附带一句“顺便统计0的个数”。比如 n 10二进制是 1010那么 1 的个数是 20 的个数也是 2。n 12二进制 11001 的个数是 20 的个数同样是 2。看起来对称、简单但面试官真正想看的是你能不能从“一个个数”想到“用位运算一次消掉一个1”再想到查表和分治这种更工程化的方案。这道题还有个让人哭笑不得的特点同一个函数名在不同题目里口径差很远。有的题目规定“统计 32 位 int 中所有位上的1”有的说“去掉前导0后有效二进制位里的1”还有的直接给一个字符串“0001010”让你数字符0和字符1的个数。所以动手写代码之前先花十秒钟把口径确认了能省掉后面一大片debug时间。1.2 三种统计口径我把最常见的口径整理成三类你后面看任何资料都可以先对号入座固定字长口径以 uint32_t 为例32位全部参与统计包括最高位的符号位当无符号处理时它也是普通数据位。此时0的个数 32 - 1的个数因为每一位非0即1。有效位口径先找到二进制里最高位的1只统计从最高位1到最低位之间的位。比如 5 的二进制是 101有效位有 3 位1 的个数是 20 的个数是 1。字符串口径给你一个二进制字符串直接遍历统计字符‘0’和‘1’。这个时候“00101”的开头两个0到底算不算有效位完全取决于题目描述。我自己的习惯是写核心函数之前先写几个具体例子摆在注释里比如“5(101) - 1的个数2, 0的个数1”然后把测试用例也一并写好。这样就算后面换了思路校验标准也没变。1.3 边界条件0、负数、字长边界条件是这类题目最容易翻车的地方。先看 n 0有效位口径下0 没有最高位的1通常约定 1 的个数为 0有效位数也是 0固定字长口径下32位全是0所以1的个数0、0的个数32。两种结果差很多但都是“合法”的关键看约定。再看负数。C/C 里 int 是补码存储的-1 的 32 位二进制全部是 1所以 __builtin_popcount(-1) 结果是 32。很多教材写“统计一个整数的二进制中1的个数”时默认是正整数但现实里你传一个负数进去编译器不会报错结果却可能和你想的完全不一样。安全的做法是函数参数直接写成 uint32_t或者调用前强制转换。最后是字长。同一个数在 32 位和 64 位下统计“固定字长0的个数”结果完全不一样。写工程代码要用 uint32_t、uint64_t 这种固定宽度类型别图省事写 int否则在 64 位机器上可能踩到意想不到的坑。2. 统计1的个数五种方案层层递进2.1 逐位扫描最容易理解和实现最直白的方案就是循环每一位。以 32 位为例循环 32 次每次把最低位取出来检查然后右移一位。int popcount_naive(uint32_t x) { int cnt 0; for (int i 0; i 32; i) { cnt (x i) 1; } return cnt; }这里有个必须注意的细节右移操作要放在固定循环里不要写while (x)然后x 1。因为如果 x 是有符号数且为负数右移是算术右移符号位会不断补1循环永远结束不了。即使你用了无符号数while (x)对于 x 0 会直接跳过结果虽然正确但逻辑上不统一。还可以用另一种写法x (x - 1)的思路以后再讲这里说一个最实用的逐位变体int popcount_while(uint32_t x) { int cnt 0; while (x) { cnt x 1; x 1; } return cnt; }它只循环到最高位的1为止对于小的正整数会比固定32次快一点。时间复杂度 O(有效位数)空间 O(1)。如果机器上没有任何内置函数而数字又比较小这个写法足够用了。2.2 Brian Kernighan 法一次消掉一个1接下来是最经典的 Brian Kernighan 算法。核心就一条x (x - 1)可以把二进制中最右边那个 1 变成 0。循环多少次就有多少个 1。这个技巧我在很多系统代码里见过树状数组的 lowbit 操作也跟它有千丝万缕的关系。先解释为什么x (x - 1)能消掉最低位的1。假设 x 的二进制是...100...00最低位的1在第 k 位那么 x-1 变成...011...11也就是说第 k 位的1借位变成了0第 k 位右边所有0都变成了1高位保持不变。按位与之后第 k 位和右边的低位全部归零高位保持原样。整个操作恰好消去了这一个1。举个例子x 12二进制 1100。x - 1 1011二者相与得到 1000也就是 8。第一次循环后 x 88 - 1 70111与 8 相与得 0。一共循环 2 次正好是 12 中1的个数。int popcount_kernighan(uint32_t x) { int cnt 0; while (x) { x (x - 1); cnt; } return cnt; }时间复杂度是 O(1的个数)对于二进制中1比较稀疏的数字非常快。比如 x 0x8000000032位里只有一个1循环一次就结束比固定32次的逐位扫描快得多。这也是我处理位图、判断“某一位是否置位”时最常用的工具。2.3 查表法用空间换时间如果一段代码要高频调用 popcount比如每秒几百万次逐位循环和 Kernighan 就不太够看了。查表法是最容易理解的优化提前算好每个字节8位里有多少个1存进一个256项的数组统计32位整数时把它拆成4个字节分别查表再加总。建表方式很简单利用递推关系一个8位数的1个数等于最低位的1加上剩下高7位的1个数。代码这样写int table[256]; void build_table() { for (int i 1; i 256; i) { table[i] (i 1) table[i 1]; } } int popcount_table(uint32_t x) { return table[x 0xff] table[(x 8) 0xff] table[(x 16) 0xff] table[(x 24) 0xff]; }这个方案的实际效果很稳。256项的数组只占256字节缓存友好拆成4次查表和3次移位、3次与运算比逐位循环的32次操作少多了。如果你对性能要求更极端可以生成16位表65536项约128KB把32位整数拆成两次查表。再往上就不建议了32位表有4G项内存直接爆炸。查表法的设计思路其实代表了一种通用思想先离线算好小规模问题的答案在线时直接取。后面布隆过滤器、动态规划预处理很多都是这个套路。2.4 分治掩码法手写版 O(1)不想开数组又想极致压缩指令数那就用分治掩码法。它不查表而是通过一组精心构造的掩码把“统计1的个数”这个任务不断拆分成相邻小组求和。核心思路是先把32位数看成16个2位的组用掩码 0x55555555二进制 01 01 01...分别取出每个2位组里的低位和高位把它们相加这样每个2位组就保存了原来两位中1的个数。接下来用 0x333333330011 0011...把相邻的2位组合并成4位组再用 0x0f0f0f0f、0x00ff00ff、0x0000ffff 逐层向上合并最后整个32位数就是答案。int popcount_parallel(uint32_t x) { x (x 0x55555555) ((x 1) 0x55555555); x (x 0x33333333) ((x 2) 0x33333333); x (x 0x0f0f0f0f) ((x 4) 0x0f0f0f0f); x (x 0x00ff00ff) ((x 8) 0x00ff00ff); x (x 0x0000ffff) ((x 16) 0x0000ffff); return x; }我拿 45二进制 00101101演示一遍。第一步00101101 01010101 00000101(00101101 1) 01010101 00010100相加得到00011001。此时每2位组里的值分别是 0、1、2、1也就是原来每两位中1的个数。第二步x 00110011 00010001(x 2) 00110011 00000010相加得到00010011每4位组的1个数分别是1和3。第三步用 0x0f0f0f0f 合并低位4位为3高4位为1相加就是4。实际上 45 的二进制正好有4个1。乍一看有5步每一步只是常数次位运算所以时间复杂度是严格的 O(1)。而且分治过程没有分支、没有循环在那些没有硬件 popcount 指令的嵌入式平台这几乎是纯软件方案里最快的一种。缺点是掩码容易写错0x55555555、0x33333333 这种数字一旦抄错一位结果完全不对。我的建议是写完之后用几个已知答案的测试用例跑一遍再上线。2.5 内置函数把专业的事交给编译器如果你不是在做笔试而是在写业务代码优先级最高的一定是语言自带的 popcount 实现。因为现代CPU基本都有专门指令编译器会把内置函数直接编译成一条指令比任何手写方案都快。不同语言和编译器的入口我整理了一下语言函数说明C/C (GCC/Clang)__builtin_popcount(x)32位版本C/C (GCC/Clang)__builtin_popcountll(x)64位版本C STLstd::bitset32(x).count()通用、可读性好JavaInteger.bitCount(x)int 类型Gobits.OnesCount32(x)/bits.OnesCount64(x)来自 math/bits 包Python 3.10x.bit_count()int 内置方法Python (通用)bin(x).count(1)慢但直观C#System.Numerics.BitOperations.PopCount(x).NET 5需要说明的是笔试或面试时如果直接调内置函数很多考官会追问一句“你知道内部怎么实现吗”。所以前面四种手写方案还是有价值的至少你要能说清楚 Kernighan 和分治掩码的原理。我在面试别人时更喜欢看候选人能不能先给出暴力解再一步步优化到查表或分治这能反映一个人对性能的敏感度。3. 统计0的个数三种口径的完整思路3.1 固定字长用总位数减1的个数固定字长是最简单的情况。既然每一位非0即1那么在一个 uint32_t 里0的个数就是 32 减去1的个数。这个关系看起来像废话但它能让你少写一半代码。直接复用上一章的 popcount 函数int count_zeros_fixed32(uint32_t x) { return 32 - popcount_kernighan(x); }64位版本把 32 改成 64 就行。这里要提一个细节如果你用有符号 int 接收参数你得到的是“算术意义上的十进制数”而不是“二进制位模式”。举例来说0xFFFFFFFF直接赋给 int 是 -132 - popcount((uint32_t)-1) 会得到 0看起来没问题但如果你先对负数取了绝对值再统计结果就全乱了。所以固定字长统计一定要用无符号类型。3.2 有效位内先数出最高位的1在哪很多时候我们不关心前导0。比如 5 的二进制是 101如果按32位统计0有30个但按有效位统计0只有1个。工程里“有效位内的0”更常用因为前导0只是定长存储的产物没什么信息量。计算步骤分两步先求有效位数 k再算 k - popcount(x)。求有效位数最直接的写法是循环右移但更快的写法是用内置函数数前导零int count_zeros_effective(uint32_t x) { if (x 0) { return 0; // 特殊约定看你题目怎么定义 } int k 32 - __builtin_clz(x); // 有效位数 int ones popcount_kernighan(x); return k - ones; }__builtin_clz(x)返回从最高位开始到第一个1之间0的个数对 5101来说返回值是 2932 - 29 3也就是说 5 的有效位数是3。然后 3 - 2 1就是有效位里0的个数。要注意的是__builtin_clz(0)在 GCC 文档里属于未定义行为所以先判断 x 0 再调用是个好习惯。3.3 前导零与尾随零两个被低估的指标除了总的0个数有些场景还关心这些更细分的指标前导零个数__builtin_clz(x)表示最高位1之前有多少个032位下对于 121100结果是 28。尾随零个数__builtin_ctz(x)表示最低位1后面连续0的个数。121100的尾随零是2因为最低位往右看有两个0。尾随零在工程里非常有用。树状数组里x -x能取出最低位的1想进一步知道它后面有几个0就是__builtin_ctz(x)。判断一个数能否被 2 的幂整除、扫描位图时跳过连续空闲块也经常用到 ctz。手写版本也不难。尾随零可以循环右移判断前导零可以二分逼近但性能不如内置指令。我的看法是这些函数在主流编译器里都有高性价比实现没必要重新造轮子理解语义然后正确调用就够了。3.4 二进制字符串最朴素但最容易理解有时候题目不给你整数而是直接给你一个二进制字符串比如00101101。这时候就不要跟位运算较劲了直接遍历统计字符s 00101101 ones s.count(1) zeros s.count(0) print(ones, zeros) # 4 4注意这种写法统计的是“字符串里所有0和1”包括前导0。如果题目说的是“去掉前导0”你需要先去掉开头连续的0再统计或者写一个strip逻辑s s.lstrip(0) or 0另外用 Python 的bin(x)把整数转字符串时负数会得到-0b101这样的形式直接count(1)会把负号排除在外但正负号的语义问题比统计本身更复杂。字符串场景下我建议先把数据形态确认清楚再统计避免做无用功。4. 这些“位数统计”到底用在哪4.1 汉明距离两个编码差多少汉明距离定义很简单两个等长编码对应位不同的个数。计算方式更简单两个数异或之后统计1的个数。int hamming_distance(uint32_t a, uint32_t b) { return popcount_parallel(a ^ b); }比如 a 50101b 30011异或得到 60110里面有两个1所以汉明距离是2。这个指标在图像感知哈希、通信纠错、指纹比对里非常常见。我之前做过一个图像去重模块把每张图缩到8x8、算完哈希之后就是靠汉明距离判断两张图相似度核心循环里全是 popcount性能优化之后速度提升了近一个数量级。4.2 布隆过滤器与bitmap存储领域的刚需布隆过滤器用一个大位数组表示集合插入元素时把 k 个哈希位置置1查询时检查这 k 个位置是否全为1。位数组里1的总数不是用户直接需要的东西但在评估过滤器“满不满”、估算元素个数、决定是否需要扩容时统计1的个数就成了关键操作。没有 popcount你就得傻乎乎地遍历整个字节数组浪费大量时间。类似需求也出现在内存管理。很多存储系统用 bitmap 管理页分配0表示空闲、1表示占用。分配内存时要找连续空闲块扫描时如果能把位图按 64 位一组处理配合ctz快速跳过连续1性能会好很多。这段内容想表达的是位运算里的0和1计数不是面试造火箭而是很多底层系统的基本构件。你写多了会发现popcount、clz、ctz 这三兄弟出场率极高。4.3 状压DPmask中有几个元素被选中状态压缩动态规划里用一个整数 mask 表示集合状态第 i 位是1表示第 i 个元素已选中。这时候统计 mask 里1的个数本质上就是在统计“当前状态下已经选了几个元素”这叫集合的 popcount。举个例子枚举一个 5 元集合中所有大小为 3 的子集int n 5; for (int mask 0; mask (1 n); mask) { if (__builtin_popcount(mask) 3) { // 处理当前大小为3的子集 } }像 TSP、旅行商问题、任务分配的很多状态转移都要用这个数值做判断或剪枝。可以说没有高效的 popcount状压DP的很多代码会变得又慢又丑。4.4 进阶变体统计区间内所有数的1个数总和很多面试官不满足于给你单个 n 统计位数会直接把问题升级成“给定 [L, R]统计区间内所有整数二进制表示里1的个数总和R 最大到 1e9。”暴力做法是遍历区间内每个数分别统计复杂度 O((R-L1) * 位数)。L 到 R 一大就完全跑不动。标准解法是按位统计先实现一个函数 f(N)统计 0 到 N 里所有数第 k 位为1的次数再对所有位求和。第 k 位的1出现规律是一个循环每 2^(k1) 个数一个周期每个周期里前 2^k 个数该位为0后 2^k 个数该位为1。推导出公式long long count_ones_upto(long long N) { long long ans 0; for (int k 0; (1LL k) N; k) { long long cycle 1LL (k 1); long long full (N 1) / cycle; long long rem (N 1) % cycle; ans full * (1LL k); ans max(0LL, rem - (1LL k)); } return ans; }区间 [L, R] 的结果就是count_ones_upto(R) - count_ones_upto(L - 1)。这个公式的推导过程很值得自己手推一遍它背后的“周期性”思想比背代码有用得多。面试时能写出这个印象分通常会高不少。5. 实操中常见的坑与排查技巧5.1 有符号数补码是第一个大坑我见过太多人在这个点上翻车。C/C 里 int 是补码存储-1 的32位二进制全是1popcount(-1) 的结果是32。你用bin(-1)在 Python 里看却是-0b1count(1) 的结果变成1。两种语言对“负数的二进制表示”语义完全不同。稳妥的处理方式统一用无符号类型或者显式掩码。C 里把参数声明成 uint32_tJava 里直接用Integer.toBinaryString(-1)你会发现它是 32 个1跟bitCount(-1)32一致因为 Java 的 int 就是定长补码。Python 的int.bit_count()对负数会报错想统计补码形式就得先转成正的掩码形式x -1 x 0xffffffff # 等价于把Python int变成32位补码的无符号表示 print(x.bit_count()) # 32这个话题一定要想清楚你统计的是“数学意义上的二进制字符串”还是“内存里的补码位模式”。不同场景要求不同但代码必须先约定好。5.2 语言差异右移、类型宽度都有坑有符号数右移在不同语言里行为不一样。C/C 对有符号负数是算术右移高位补1对无符号数是逻辑右移高位补0。Java 的是算术右移才是无符号右移。如果统计函数里用while (x)配合x 1在遇到负数时很可能死循环。类型宽度也容易出问题。同样的写法在32位平台 int 是32位在64位平台 int 还是32位但 long 就从32位变64位。查表和分治掩码都是针对固定宽度设计的如果你拿 64 位数去跑 32 位的分治函数高位直接丢掉结果必然错误。所以我写这类函数时一定会用 uint32_t、uint64_t并在函数名或注释里标明宽度。5.3 性能对比别盲目迷信某个方案不同方案在特定场景下各有优势我直接给一张对比表方案时间复杂度实现难度适用场景逐位扫描O(bits)低教学、无内置函数KernighanO(popcount)低数字稀疏、位图扫描查表O(bits/8)中高频调用、可接受查表分治掩码O(1)高极致性能、无硬件指令内置函数接近O(1)很低日常开发首选实际遇到的高频场景比如哈希计算、大数据扫描少量调用时这些差异根本看不出来但你要在一个循环里调用某个函数几百万次那差距就会被放大。我在处理一个 bitmap 扫描模块时把逐位统计改成 Kernighan 配合 ctz 跳块耗时直接下降了一个数量级。需要提醒一句不是所有场景都值得优化。业务代码里一个函数每秒被调用几百次优先考虑可读性就行只有 profiling 显示它是热点时才值得上分治或者查表。5.4 手写函数时的测试用例清单如果你准备把手写版本用在生产环境最好准备一组测试用例。我的常规清单输入二进制popcount 期望值备注000边界111最小正数2101最低位为03112低位全12551111111188位全12561000000001第9位为10x800000001 后接31个01仅最高位为10xFFFFFFFF32个132全1写代码时可以对照 Python 的bin(x).count(1)做交叉验证随机生成几千个大数跑一遍比对结果。分治掩码这种代码一旦掩码敲错了第一步就会出问题所以测试不能省。还有64位版本的分治掩码是 0x5555555555555555、0x3333333333333333、0x0f0f0f0f0f0f0f0f、0x00ff00ff00ff00ff、0x0000ffff0000ffff、0x00000000ffffffff别把32位的掩码直接套进去。最后分享一个个人习惯。我平时写这类“简单”题目反而不爱上来就写最优解而是会把暴力版本、优化版本、内置版本全部写在同一份测试文件里用随机数据互相对拍。这样既能验证每种实现的正确性又能在调试时直观感受到性能差异。位运算这种东西光看别人的讲解是记不牢的亲手把 Kernighan 推导一遍、把分治演算一遍才能真正变成自己的东西。你再遇到“0和1的个数”相关的题不管是考原理还是考工程都能游刃有余。