最近做一个位图压缩工具需要在几百万字节的二进制数据里统计每个字节中0和1的个数用来估算熵值、调整压缩策略。这个需求让我把“0和1的个数”这个话题彻底翻了一遍——单看题目它像是一道入门级别的编程题但真做起来统计方式、负数行为、位宽差异、性能取舍每一个环节都有细节。这篇就围绕“统计二进制中0和1的个数”展开聊聊它到底解决什么问题、有哪些算法可以选、负数和大整数有哪些坑、以及实际项目里怎么做性能调优。1. 统计0和1的个数到底解决什么问题先把“统计0和1的个数”这件事放回真实场景里。很多开发者第一次接触它是因为面试题给一个整数判断它的二进制表示里有几个1。但离开面试题之后这个操作在工程里的出场率远比想象中高。1.1 最直接的应用校验与哈希两个二进制串之间的汉明距离定义为对应位不同的个数。计算方式很简单把两个数异或再统计结果中1的个数。感知哈希pHash、SimHash、图像相似度对比、纠错码的纠错能力分析到处都在用这个操作。统计1的个数在英文里通常叫 popcountpopulation count很多CPU指令集甚至直接提供了硬件指令比如 x86 的 POPCNT。另一个常见场景是奇偶校验。串口通信、RAID阵列、ECC内存里的校验位计算本质上就是统计一组数据里1的个数是奇数还是偶数。单个字节的1的个数取模2就是最常见的奇偶校验位。很多底层库不会直接给“校验位”接口而是让你自己 popcount 然后取最低位。1.2 压缩与熵估计统计0的个数同样关键做无损压缩时一个数据块里0和1的分布直接决定了压缩率的上限。如果一段二进制数据里99%的位都是0那它非常适合用游程编码或者稀疏位图如果0和1几乎五五开那大概率已经接近熵极限硬压也压不了太多。计算信息熵就需要知道0的比例和1的比例H -p0 * log2(p0) - p1 * log2(p1)p0 就是0的个数除以总位数。这个值在预压缩判断里很实用一个数据块熵值如果小于某个阈值说明还有压缩空间如果接近1直接跳过免得浪费CPU。我在那个位图压缩工具里就是这么用的。先把整个数据块分成若干小段每段统计0和1的个数算出熵值。只有熵值低的分段才走压缩流程熵值高的直接原样存储。这个预筛选看起来不起眼但能省掉大量无意义的压缩尝试。1.3 位级协议与状态检查硬件寄存器经常用单个bit表示一个开关状态比如“写保护”“中断标记”“设备在线”。读取一批寄存器值后统计它们里面有几个bit处于高电平可以快速判断设备整体状态有几个通道告警、有多少设备在线。这种场景不要求复杂算法但要求统计得准尤其是寄存器值可能是负数时后面单独讲。2. 统计二进制1个数的四种主流算法与复杂度权衡统计1的个数算法不少从最朴素的逐位循环到常数时间的分治法都有。我按实际工程中常见的四类来写。2.1 朴素循环最容易写也最容易忽视位宽最直接的办法一位一位右移然后和1做与运算int count_ones_naive(uint64_t x) { int count 0; while (x) { count x 1; x 1; } return count; }这个写法的问题是当x的高位全是0时它还是会一直移位到x变成0为止。如果传入一个uint64_t它最多循环64次也还好。但如果在Python这类无限位宽的整数上一个很小的数也会被算成整型字长实际上逐位循环会受表示影响。在C/C里要注意循环变量类型用int还是uint64_t统计很好理解。它的时间复杂度是O(位数)实现成本最低适合数据量极小、对性能没要求的场景。2.2 Brian Kernighan算法只循环1的个数次这是面试里常考的一种优化每次去掉最右边的一个1直到变成0。int count_ones_kernighan(uint64_t x) { int count 0; while (x) { x x - 1; count; } return count; }核心原理是 x - 1 会让最低位的那个1变成0同时该位右侧的所有0变成1再和原来的x做与运算就等于把最右边的1清掉了。这个算法循环次数等于二进制里1的个数如果x是0循环一次都不执行。实际项目中如果1的密度很低比如大量数据只有少数几个bit置位这个算法表现得非常快。缺点也很明显如果1的个数接近位宽它并不比朴素循环快多少而且每次都有一串减法、与运算跳转预测也不好做。2.3 查表法空间换时间的经典思路预处理一张256项的查表每个索引对应0~255这个字节中1的个数static unsigned char ones_table[256]; void init_ones_table(void) { for (int i 0; i 256; i) { ones_table[i] (unsigned char)count_ones_kernighan(i); } } int count_ones_by_table(uint64_t x) { return ones_table[x 0xFF] ones_table[(x 8) 0xFF] ones_table[(x 16) 0xFF] ones_table[(x 24) 0xFF] ones_table[(x 32) 0xFF] ones_table[(x 40) 0xFF] ones_table[(x 48) 0xFF] ones_table[(x 56) 0xFF]; }查表法的时间复杂度是O(字节数)也就是固定8次查表加5次加法。理论上很快而且实现简单。实际测试中它受两个因素影响查表是随机内存访问如果数据规模很大、表不在cache里性能会打折另外函数调用、整数组合也有开销。2.4 分治法SWAR无查表、无分支、常数时间如果要在大量数据上计算popcount最值得掌握的是SWARSIMD Within A Register写法。它的思路是把64位整数拆成很多小组每组内统计1的个数然后逐层合并。uint64_t swar_popcnt(uint64_t x) { x x - ((x 1) 0x5555555555555555ULL); x (x 0x3333333333333333ULL) ((x 2) 0x3333333333333333ULL); x (x (x 4)) 0x0F0F0F0F0F0F0F0FULL; x x (x 8); x x (x 16); x x (x 32); return (uint64_t)(x 0x7F); }看第一行可能有点晕拆开解释x 1 把每两个bit的高位挪到低位和0x5555...做与运算只保留每个bit对中的低位。原x减去这个结果等价于对每个bit对做加法两位里原本的1个数直接变成了两位二进制表达。这就是“每个2bit小组内统计1个数”。后续每一步都是把相邻小组的结果加起来。第一行之后每个2bit小组存的是0~2之间的值第二行把相邻的2bit组合并成4bit组能表达0~4第三行合并成8bit组最后三次右移加法把8个8bit组逐级合并成总计数。整个过程没有任何分支也没有查表非常适合流水线执行。现代编译器对这类位运算代码会优化得很好而且如果确定目标CPU支持POPCNT可以直接内建函数。下面这张表把四种算法放在一起对比算法时间复杂度分支内存访问适用场景朴素循环O(位数)每bit一次判断无教学、临时调试KernighanO(1的个数)每个1一次判断无稀疏数据查表法O(字节数)无随机查表字节流批量、位数固定SWARO(1)无无高频调用、批量流式3. 0的个数不难难在负数与无符号数的坑统计0的个数常规做法是确定一个位宽然后0的个数 位宽 - 1的个数。这句话本身没问题但一旦涉及负数和不同类型歧义就来了。3.1 “二进制表示”到底指哪个二进制表示一个正数转成二进制所有人脑子里都是标准写法。但负数就麻烦了。在计算机里负数用补码表示。以8位为例-1的补码是11111111里面1的个数是80的个数是0。可是很多人写算法的时候直接用十进制转二进制的字符串来数-1可能会被转成-1这种带符号的字符串然后数出来0个1。这就是典型的“没有明确语义”的坑。C/C里更隐蔽int是16位还是32位由平台决定表示-1时16位下是111111111111111132位下是11111111111111111111111111111111统计结果差一倍。所以做这类统计第一步一定是明确位宽最好全部转成无符号整型再操作。int count_ones_unsigned(uint32_t x) { x x - ((x 1) 0x55555555U); x (x 0x33333333U) ((x 2) 0x33333333U); x (x (x 4)) 0x0F0F0F0FU; x x (x 8); x x (x 16); return x 0x3F; }这里入参是uint32_t负数传入时会被隐式转换成无符号数效果和“把负数按32位补码看待”一致。3.2 不同语言对负数的popcount处理完全不同这是我在实际开发里踩过的一次大坑。在C里把负数传给uint64_t参数会得到补码位模式统计结果符合预期。但在Python里直接数一个负数的bit就完全不是一回事。Python从3.10开始提供int.bit_count()官方文档明确说明它返回的是整数绝对值对应的二进制表示里1的个数。也就是说print((-1).bit_count()) # 输出 1 print((-3).bit_count()) # 输出 2这跟C里把负数转成无符号数后统计的结果不一样。为什么要这样设计因为Python的int是任意精度负数的补码在高位是无限延伸的1。如果按补码语义统计-1会有无穷多个1这个结果没法作为有限整数返回。Python团队索性定义为统计绝对值让结果是有限值。这个设计很合理但如果你是从C/C转过来极其容易踩坑。Java里又是另一套int有32位定长Integer.bitCount(-1)返回32它内部就是把int当作补码来看。long版本Long.bitCount返回64。Go的math/bits.OnesCount64也是按固定位宽补码语义来数负数会得到64。所以“同样的代码”换语言结果可能完全不同。写跨语言逻辑时一定要确认底层的语义。3.3 字节流场景里更要先转无符号做二进制协议解析的时候经常拿到的是int8_t或者byte切片里的负数。比如Java的byte类型有符号范围-128~127。一个字节0x80在Java里是-128如果直接Integer.bitCount(-128)统计的是int 32位的补码得到25这不是你想要的“这个字节里1的个数”。正确做法是先做无符号化byteValue 0xFF得到0~255的整数再统计。我自己写字节流工具时统一先写一个函数负责“把字节转成无符号整数”后续所有统计只针对无符号整数彻底避开符号位的干扰。3.4 统计有效位里的0还得先定义“有效位”这个需求在协议开发里很常见给定一个数值想知道它有效二进制位里0和1各有多少。比如十进制的5有效位是3位101里面2个1、1个0。很多人直接拿“位宽”减popcount位宽却拿不准是系统的int位宽还是这个数实际占用的最短位数没有统一标准。我习惯这样处理先确定有效位宽用最高位为1的位置加1来计算。int bit_length(uint64_t x) { int len 0; while (x) { len; x 1; } return len; }拿到有效位宽后有效位里0的个数 bit_length(x) - popcount(x)。注意如果x是0有效位宽是0这时的0的个数是0而不是1语义要提前定义清楚。我在文档里会计算两种口径一种是固定32/64位全局位宽一种是有效位宽避免团队里理解不一致。4. 性能实战查表法在真实数据集上的调优聊完语义和正确性回到性能。我那个位图压缩工具有一个高频操作在读取数据流的同时对每段数据做0/1统计。数据规模是几百万字节级别最开始用的是最朴素的逐字节查表。后来发现瓶颈不在数据读取而在统计。这才开始认真做性能调优。4.1 初始实现的性能问题初始代码大概是这样的size_t ones 0; uint8_t *p data; for (size_t i 0; i len; i) { ones ones_table[p[i]]; }处理128MB数据耗时比预期高不少。用perf分析后发现ones_table虽然只有256项但频繁随机索引L1缓存命中率并不高。因为表很小其实应该常驻缓存但问题在于编译器对p[i]的索引和ones_table的基址都没有做更激进的优化加上每个字节都要做一次64位加法。4.2 一次减少查表次数的优化按4字节/8字节处理字节流的统计不需要严格按字节来可以把4个字节拼成一个uint32_t一次性查出4个字节各自的结果。查表法从原来查8次降成查2次或者一次查16字节降成4次。配合上内存拷贝数据吞吐快了很多。uint64_t ones_in_u32(uint32_t v) { return ones_table[v 0xFF] ones_table[(v 8) 0xFF] ones_table[(v 16) 0xFF] ones_table[(v 24) 0xFF]; }这个优化效果明显但不是质变。进一步的做法是直接使用64位查表预处理一张16位的表把两个字节合并成一个16位索引表大小65536项查询次数再减一半。表大小虽然变大但对现代CPU来说64KB依然能放进L2缓存效果通常比256*8次查询更好。方案每次统计的查表次数表大小实测吞吐128MB8比特表逐字节1256B约850ms8比特表4字节合并4256B约420ms8比特表8字节合并8256B约380ms16比特表8字节合并464KB约290ms16比特表在流式数据上收益最大因为索引更少CPU前端压力小。不过如果运行环境L2缓存很小64KB的表可能反而拖慢。这个要结合目标硬件选不是越大越好。4.3 最终选择SWAR避免随机访问在大批量场景下SWAR最终表现比16比特查表更稳定。因为它完全没有随机访问数据流式进来寄存器里一轮计算就出结果。代码在前面已经写了把入参从uint64_t换成连续内存的循环版本即可。uint64_t swar_popcnt(const uint8_t *p, size_t len) { uint64_t total 0; for (size_t i 0; i len; i 8) { uint64_t v; memcpy(v, p i, 8); total popcnt_u64(v); } return total; }注意memcpy而非直接指针强转是为了避免未对齐访问问题。现代x86支持未对齐访问但ARM某些架构对未对齐处理差一些统一用memcpy更稳妥。编译器在优化开启后这个memcpy通常会被优化成一条load指令没有实际函数调用开销。实测下来SWAR版本在128MB数据上的耗时可以压到200ms以内比最初的逐字节查表快了4倍多。而代码量也就十几行不需要额外表也不用担心缓存问题是我最终在项目里用的方案。4.4 如果目标机器支持POPCNT最后提一个很容易忽略的点现代x86和ARMv8.1部分都有硬件popcount指令。GCC/Clang里可以用__builtin_popcountllMSVC用__popcnt64。如果编译目标明确是较新的CPU直接用硬件指令写出来的代码会少得多#include stdint.h int ones __builtin_popcountll(data);性能上硬件指令通常是最快的。但要注意兼容性如果程序要跑在旧CPU上这类指令会触发非法指令异常。我一般会运行时检测CPU特性支持就用硬件指令不支持就退回SWAR。这个“检测降级”的框架在性能敏感场景很值。5. 边界case与测试用例设计别再被负数绊倒写统计0和1个数的功能正确性测试比算法本身更需要关注。我把踩过的边界case整理成一张测试矩阵写单元测试时直接照着填。5.1 基础边界case矩阵输入预期32位补码语义说明01的个数0高位0个数32全011的个数10的个数31最低位为10xFFFFFFFF1的个数320的个数0全10x800000001的个数10的个数31最高位为1负数-11的个数320的个数0按32位补码看51011的个数20的个数1有效位3有效位统计这个表里最值得注意的就是-1和0x80000000。如果函数入参是int-1转成uint32_t后有32个1如果函数内部用int右移就需要特别小心有符号右移会补符号位。5.2 有符号右移的经典陷阱C里对负数做右移行为是implementation-defined常见编译器都是算术右移也就是高位补符号位的1。这会导致一个常见bugint count_ones_bad(int x) { int count 0; while (x) { count x 1; x 1; // x是负数时右移补1永远不等于0死循环 } return count; }如果输入是-1这个循环永远不会结束。要修要么把参数改成unsigned int要么右移改成逻辑右移。C里没有直接的无符号右移运算符最稳妥的做法就是一开始就转成无符号类型。Java里也有同样的坑int是符号数右移用补符号位用才是补零的逻辑右移。统计二进制位时必须选对。C#、JavaScript也都类似只是运算符细节不同。任何涉及“逐位右移去数bit”的函数最好都约定用无符号语义。5.3 大整数和无符号长整型64位长度的边界0xFFFFFFFFFFFFFFFF全1对应无符号整型最大值统计结果应该是64。用有符号long直接比较可能会因为溢出或者签名问题出错。我在C/C里习惯用uint64_t在Java里用long配合Long.bitCount没问题。但是如果你写通用函数、传入的是高精度语言的大整数就要单独处理“无限位宽”问题。Python的int没有固定位宽。如果你要统计“64位视图”下的1个数得先做掩码x ((1 64) - 1)把超出部分截断然后再统计。下面的代码演示了这种按固定位宽统计的写法def popcnt_fixed(x: int, bits: int 64) - int: mask (1 bits) - 1 return (x mask).bit_count()这种写法在跨语言结果对拍时非常有用。5.4 统计0的个数时的一致性统计0的个数一定要和“位宽口径”保持一致。用32位口径时0x80000000有31个0用8位字节口径时同一个字节0x80就有7个0。我在项目里把“位宽口径”作为参数传进去而不是在函数内部硬编码避免别人调用时误解。再分享一个小经验做单元测试时不要只测整数也要测字节切片。把整个字节流每个元素的0/1个数累加起来跟直接对字节流做整体统计的结果对比应该一致。这个“整体一致性校验”能抓出很多循环边界、分组处理错位之类的bug。写在最后说句实在话“0和1的个数”这个题目大多数时候被当成练习题但真正在项目里用起来坑几乎都在“负数和位宽”上。我最后选型时没有用最花哨的方案而是把“无符号化处理”放在第一位算法上选了SWAR加运行时POPCNT降级数据和代码都稳。如果你的场景也需要高频统计0/1分布我建议先从无符号化开始再根据数据规模选择查表还是SWAR。提前把这些边界想清楚比事后debug省心太多了。