统计二进制中0和1的个数：算法、陷阱与性能优化

最近做一个位图压缩工具，需要在几百万字节的二进制数据里统计每个字节中0和1的个数，用来估算熵值、调整压缩策略。这个需求让我把“0和1的个数”这个话题彻底翻了一遍——单看题目，它像是一道入门级别的编程题，但真做起来，统计方式、负数行为、位宽差异、性能取舍每一个环节都有细节。这篇就围绕“统计二进制中0和1的个数”展开，聊聊它到底解决什么问题、有哪些算法可以选、负数和大整数有哪些坑、以及实际项目里怎么做性能调优。

1. 统计0和1的个数，到底解决什么问题

先把“统计0和1的个数”这件事放回真实场景里。很多开发者第一次接触它是因为面试题：给一个整数，判断它的二进制表示里有几个1。但离开面试题之后，这个操作在工程里的出场率远比想象中高。

1.1 最直接的应用：校验与哈希

两个二进制串之间的汉明距离，定义为对应位不同的个数。计算方式很简单：把两个数异或，再统计结果中1的个数。感知哈希（pHash）、SimHash、图像相似度对比、纠错码的纠错能力分析，到处都在用这个操作。统计1的个数在英文里通常叫 popcount（population 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，最值得掌握的是SWAR（SIMD 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，可以直接内建函数。

下面这张表把四种算法放在一起对比：

3. 0的个数不难，难在负数与无符号数的坑

统计0的个数，常规做法是：确定一个位宽，然后0的个数 = 位宽 - 1的个数。这句话本身没问题，但一旦涉及负数和不同类型，歧义就来了。

3.1 “二进制表示”到底指哪个二进制表示

一个正数转成二进制，所有人脑子里都是标准写法。但负数就麻烦了。在计算机里，负数用补码表示。以8位为例，-1的补码是11111111，里面1的个数是8，0的个数是0。可是很多人写算法的时候，直接用十进制转二进制的字符串来数，-1可能会被转成"-1"这种带符号的字符串，然后数出来0个1。这就是典型的“没有明确语义”的坑。

C/C++里更隐蔽：int是16位还是32位由平台决定，表示-1时，16位下是1111111111111111，32位下是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次查询更好。

16比特表在流式数据上收益最大，因为索引更少，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_popcountll，MSVC用__popcnt64。如果编译目标明确是较新的CPU，直接用硬件指令写出来的代码会少得多：

#include <stdint.h> int ones = __builtin_popcountll(data);

性能上硬件指令通常是最快的。但要注意兼容性：如果程序要跑在旧CPU上，这类指令会触发非法指令异常。我一般会运行时检测CPU特性，支持就用硬件指令，不支持就退回SWAR。这个“检测+降级”的框架在性能敏感场景很值。

5. 边界case与测试用例设计：别再被负数绊倒

写统计0和1个数的功能，正确性测试比算法本身更需要关注。我把踩过的边界case整理成一张测试矩阵，写单元测试时直接照着填。

5.1 基础边界case矩阵

这个表里最值得注意的就是-1和0x80000000。如果函数入参是int，-1转成uint32_t后有32个1；如果函数内部用int右移，就需要特别小心有符号右移会补符号位。

5.2 有符号右移的经典陷阱

C++里对负数做>>右移，行为是implementation-defined，常见编译器都是算术右移，也就是高位补符号位的1。这会导致一个常见bug：

int 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省心太多了。