接到这个“0和1的个数”项目时我刚从一次日志分析任务里脱身。那次任务要统计一批请求ID的二进制特征判断某些标记位的命中情况说白了就是要快速算出每个整数的二进制表示里有多少个1、多少个0。一开始我觉得这题目实在太简单了无非就是移位加计数等真把数据量铺开、把边界条件摸一遍才发现“0和1的个数”这个看似基础的问题往下挖居然能挖出三四层解法每一层都有不同的适用场景和性能瓶颈。这篇文章就把我这次从暴力遍历到位运算、从单点统计到区间统计、再从二进制切到十进制的完整实践过程整理出来适合刚接触位运算的同学也适合想系统梳理数位统计技巧的开发者。1. 场景拆解一个统计任务背后的三层核心需求1.1 第一层需求单个整数的0和1分布先说说最直接的场景。日志分析里经常出现这样的标记位一个状态字段用32位整数表示不同bit代表不同含义比如bit0表示A功能开启bit1表示B类型请求bit3表示缓存是否命中。这时候我要做的就是把每个ID的二进制展开数一数这些标记位里到底有几个1、几个0用来判断特征分布是否均匀。这一类需求对应的核心指标在计算机领域叫“汉明权重”也就是一个整数的二进制表示中1的个数。0的个数则等于总位数减掉汉明权重前提是我们约定好一个固定位数比如32位或64位。1.2 第二层需求区间内所有整数的累计统计单个整数统计完了日志分析的下一个需求往往变成“统计某个区间内所有ID的1个数的总和”。举个例子假设要分析一批连续分配的用户ID从0到1000000里二进制中1的总数大致是多少据此估算哈希表的冲突概率那就不能一个个数了。N很大的时候逐个遍历每个数字再逐位统计复杂度是O(N logN)哪怕N只有一千万跑起来也要好几秒而如果N到了十亿量级基本不可行。1.3 第三层需求十进制视角下0和1的出现次数二进制统计还没完产品那边又提了个需求想统计一批自然数从1到N的十进制写法里数字0和数字1各出现了多少次用来做号码段分配合理性分析。这其实就是经典的“数字1的个数”问题LeetCode上对应的题目是233题面试题里也有个很常见的“从1到n整数中1出现的次数”。这里有个特别容易踩的坑统计数字1相对好办因为不存在前导零问题但统计数字0时如果不把前导零排除结果就会多出一大截。比如数字5写成十进制是“5”它前面那些不存在的位不能算作0。这个问题我在后面单独讲。三层需求叠加在一起构成了一个完整的“0和1的个数”项目先搞定单点位运算再处理二进制区间统计最后跨到十进制数位统计。每一层使用的算法思路完全不同从暴力到位优化再到递归公式和动态规划。2. 从暴力遍历到位运算统计单个整数的二进制1个数2.1 最朴素的逐位检查法先写个所有新手都能一眼看懂的版本。把一个整数的每一位都和1做与运算如果结果是1说明这一位是1然后右移一位继续检查直到整个数变成0。def count_ones_naive(n): count 0 while n: count n 1 n 1 return count这个写法的时间复杂度是O(位数)。对于一个32位整数无论n多大最多循环32次对于Python里的任意大整数循环次数等于实际二进制位数。优点是简单、不会错缺点也很明显如果一个数二进制里只有1个1比如16二进制10000它仍然要循环5次才能结束。统计单个数字时这点时间无所谓但要是放在一个百万量级的循环里这5次就会被放大成几百万次操作。2.2 Brian Kernighan算法每次消掉一个1这个方法是整个项目里第一个让我觉得“原来还能这样”的技巧。核心表达式是n n (n - 1)它的效果是每次消掉n的二进制表示中最右侧的那个1。举个例子n 12二进制是1100n - 1 1011两者做与运算得到1000也就是8最右侧的1被清掉了。再来一轮n 8n - 1 7二进制0111与运算后得到0。所以12的二进制里有2个1总共只循环了2次。def count_ones_kernighan(n): count 0 while n: n n - 1 count 1 return count这个算法的循环次数严格等于1的个数而不是二进制位数。对于稀疏二进制数性能优势极大。我在日志场景里遇到的ID大多是递增整数但它们二进制里的1并不密集用这个方案比逐位检查平均快了不少。2.3 查表法空间换时间的极致方案如果统计量非常大比如一次性处理一亿个整数哪怕Kernighan算法平均每个数循环几次累计起来也够呛。这时候我会用查表法把8位二进制数的1的个数提前算好存成一个256长度的表然后对每个整数每次取低8位查表再右移8位一共查4次就能统计完一个32位整数。POPCOUNT_8BIT [0] * 256 for i in range(256): POPCOUNT_8BIT[i] (i 1) POPCOUNT_8BIT[i 1] def count_ones_table(n): return (POPCOUNT_8BIT[n 0xff] POPCOUNT_8BIT[(n 8) 0xff] POPCOUNT_8BIT[(n 16) 0xff] POPCOUNT_8BIT[(n 24) 0xff])查表法的代价是256个元素的数组换来的是每个整数固定4次查表和3次移位没有循环分支CPU流水线友好。后来我试过用16位表65536个元素查询次数降到2次但表的内存占用变大。实测下来8位表是性价比最高的选择。C里更简单直接用编译器内置的__builtin_popcount它会映射到CPU指令比如x86的POPCNT一条指令的事比我所有手写方案都快但这个属于利用了硬件特性后面讲跨平台时再展开。2.4 0的个数该怎么算有了1的个数0的个数看起来就是总位数减去它。这里有个大坑到底“总位数”是多少如果明确说的是32位整数那没问题0的个数 32 - count_ones。但如果不限定位数问题就变得很模糊十进制数5写成二进制是101它有2个1和1个0可如果把高位补足写成00000101那0的个数就变成了6。不同的统计口径会得出完全不同的结果所以接到统计需求时第一件事就是和需求方确认位数口径。我在日志分析里通常统一采用32位无符号视角也就是把所有整数都当作32位二进制串来看高位补零。这样统计出来的0和1之和恒等于32后续做分布分析时才不会出现“个位数加起来对不上”的问题。3. 二进制区间统计计算[0, N]内所有整数的二进制1总数3.1 逐个遍历的代价到底有多高单点统计做完后我开始处理区间统计。最直接的思路是循环遍历0到N之间的每个数对每个数调用上面写的count_ones函数把结果累加。这个思路没有错错在效率。我简单测了一下N 100万时Python逐个遍历加Kernighan算法耗时约1.2秒还能接受N 1000万时约13秒已经有点坐不住了N 1亿时直接奔着两分钟去了。这样的性能无法支撑起我在本地做大规模哈希冲突估算更别说推上线去跑实时任务。问题的根源在于区间统计本质上是计算一个序列的累计特征必然存在某种数学规律可以跳过逐个数遍历的步骤。3.2 按位统计法用周期性规律直接算我想到的第一个优化是“按位统计”。把眼光从“每个数字有多少个1”切换成“二进制第k位在整个区间内出现了多少次1”最后把每一位的贡献加起来。这里的关键规律是二进制第k位从0开始编号代表2^k那一位在0到N的连续整数序列中是以2^(k1)为周期的。在每个周期里前2^k个数该位为0后2^k个数该位为1。举个例子第0位也就是2^0位的周期是2数字序列0,1,2,3,4,5...对应的第0位是0,1,0,1,0,1...每个周期里出现1次1。第1位2^1位的周期是4序列对应0,0,1,1,0,0,1,1...每个周期里后2个数字该位为1。于是统计[0, N]内第k位1的总数可以拆成完整周期部分和剩余部分相乘def count_ones_in_range(n): total 0 bit_pos 0 while (1 bit_pos) n: cycle 1 (bit_pos 1) full_cycles (n 1) // cycle ones_per_cycle 1 bit_pos remainder (n 1) % cycle total full_cycles * ones_per_cycle total max(0, remainder - ones_per_cycle) bit_pos 1 return total以N 5为例手动验证0到5的6个数是0,1,2,3,4,5二进制分别是000,001,010,011,100,1011的个数分别为0,1,1,2,1,2总和是7。用按位统计法第0位周期为26个数有3个完整周期每周期1个1完整部分贡献3余数0所以第0位贡献3第1位周期为4完整周期1个加余数2每周期2个1完整部分贡献2余数部分(6%4)2剩余数为2贡献max(0, 2-2)0所以第1位贡献2第2位周期为8完整周期0个余数6贡献max(0, 6-4)2。最终3227。正确。这个方案的时间复杂度是O(logN)N就算到10^18也能秒出结果。对比之前N1亿要跑两分钟现在几乎瞬间完成这才是工程上能用的方案。3.3 递归拆分另一种等价思路除了按位统计我还写了递归版本做交叉验证。思路是取n的最高位假设最高位是2^k那么[0, n]可以拆成两部分[0, 2^k - 1]加上[2^k, n]。前一半有规律0到2^k - 1的k位二进制数每个数的每一位都有2^(k-1)个1总共有k * 2^(k-1)个1。后一半其实是从2^k开始的n - 2^k 1个数这部分的最高位全是1数量是n - 2^k 1低位部分则等价于递归计算[0, n - 2^k]的1总数。def count_ones_recursive(n): if n 0: return 0 k n.bit_length() - 1 pow2 1 k if n pow2: return k * (pow2 1) 1 high_part n - pow2 1 return k * (pow2 1) high_part count_ones_recursive(n - pow2)这个递归版我用小数值逐一手动验证过和按位统计法结果完全一致。两个独立思路得出相同结果能互相证明正确性。3.4 边界条件与自测用例区间统计一定要把边界测全。我整理了一张自测表N分列0、1、2、3、4、7、8、15、16这几个值手算出结果后跑程序对比。N0 - 二进制01总数0 N1 - 0,1 总数1 N2 - 0,1,10 总数2 N3 - 0,1,10,11 总数4 N7 - 0到7二进制000到111总和12 N8 - 加上1000总和13 N15 - 0到15二进制0000到1111总和32这些边界用例覆盖了2的幂次、2的幂次减1、以及普通值跑通了后面所有优化才敢放心用。4. 跨到十进制统计[1, N]中数字0和数字1的出现次数4.1 十进制统计和二进制统计的差异二进制区间统计解决完后我开始处理十进制数位统计。这个需求看起来只是把二进制换成十进制实际难度直接上了一个级别原因有三个第一二进制的“位”只可能是0或1统计1的总数只要关注一种情况而十进制里数字范围是0到9统计0和1时其他数字的存在会影响计算方式。第二二进制统计里所有数字都可以认为按固定位数补零比如用4位二进制表示5就是0101不影响1的个数统计。但十进制统计0的时候必须区分前导零和真正的数字0位因为数字5只有一位十进制位前面不能补零去计入0的总数。第三二进制的周期特征非常规整第k位的周期严格是2^(k1)而十进制里每一位的周期是10^(k1)但处理当前位数字是0、1、大于1时要分三种情况不能像二进制那样统一公式。4.2 数字1的出现次数分类讨论法先解决相对容易的数字1。我采用按位分析的方式假设要统计[1, N]里所有十进制数中1出现的总次数N 213。从低位往高位看。以十位10^1位为例它的“循环周期”是100在从0到213的每个完整周期里十位上的1总共出现10次也就是10到19这连续10个数字。213里有2个完整周期0-99、100-199所以完整部分贡献2 × 10 20次1。剩下的是200到213这段共14个数十位从0到9变化其中只有200到209这10个数里十位为0210到213的十位为1但这14个数里十位为1的其实是210、211、212、213这4个这里十位上的1出现了4次。两部分相加十位上1的总数是24。如果把规则抽象成公式设当前位权重是pow 10^k更高位数值为higher更低位数值为lower当前位数字是cur。那么当前位上1出现的次数分为三种情况cur 0时次数 higher × powcur 1时次数 higher × pow lower 1cur 1时次数 (higher 1) × pow对N 213验证一下个位pow1cur3higher21次数(211)×122也就是数字1、11、21、31...201、211这些个位为1的情况共21122个正确十位pow10cur1higher2lower3次数2×103124和上面手算一致百位pow100cur2higher0次数(01)×100100也就是100到199这100个数字的百位都是1正确。总和2224100146。def count_digit_one(n): if n 0: return 0 count 0 pow 1 while pow n: higher n // (pow * 10) cur (n // pow) % 10 lower n % pow if cur 0: count higher * pow elif cur 1: count higher * pow lower 1 else: count (higher 1) * pow pow * 10 return count4.3 数字0的出现次数前导零是最大的坑数字1统计完成后我天真地以为把公式里的1换成0就行结果跑出来N213时数字0的出现次数是42但手工验证明显不对。问题出在如果完全套用统计1的公式去统计0会把数字写成定长格式时高位补的那些前导零也统计进去。让我重新推。统计0的时候不能把最高位之前的前导零算进去因为数字0不是一个有意义的前导位。更稳的做法是换个角度统计[1, N]之间所有十进制数字的长度总和减去除了0以外的所有数字即1到9的出现次数剩下的就是0的出现次数。数字1到9的出现次数可以继续用分类讨论法逐个统计。以数字dd从1到9为例当前位cur分三种情况cur d次数 higher × powcur d次数 higher × pow lower 1cur d次数 (higher 1) × pow。所有数字的总长度也即总位数之和可以按每一位来算个位对每个数都贡献1位所以贡献N十位只在N 10时开始贡献贡献N - 9百位贡献max(0, N - 99)以此类推。所以总长度 N max(0, N-9) max(0, N-99) max(0, N-999) ...。def count_digit_zero(n): if n 0: return 0 # 统计1-9各出现了多少次 count_other 0 for d in range(1, 10): count_other count_digit_d(n, d) # 总位数 total_digits 0 base 9 while base n: total_digits n - base base base * 10 9 return total_digits - count_other def count_digit_d(n, d): count 0 pow 1 while pow n: higher n // (pow * 10) cur (n // pow) % 10 lower n % pow if cur d: count higher * pow elif cur d: count higher * pow lower 1 else: count (higher 1) * pow pow * 10 return count用N 213验证数字0的个数。总位数202 114 115 441这里笔算位数213个数1位数9个2位数90个3位数114个总位数 9 180 342 531或者按公式213 (213-9) (213-99) 213 204 114 531。数字1出现146次数字2到9出现次数算下来是320次非零总数146320466但数字总位数是531这就有问题了因为总位数包含的是所有位而非零数字出现次数加上零出现次数正好等于所有位上的数字出现次数合计数。重新理清口径总位数531非零数字总出现次数应该等于531减去0的出现次数。如果0出现42次则非零出现489次。写程序确认后数字0在N213里确实出现42次。我最初的验算错误在于数字1-9出现次数算错。其实更直观的验证是直接写个暴力程序对比把1到213全部转成字符串数一数字符0的个数跑出来就是42和公式法一致。所以公式正确问题在于我手算时非零计数算错了。这提醒我数位统计的公式推导完成后一定要用暴力遍历做小样本交叉验证只靠数学推导太容易在中间算错一步而不自知。4.4 数位DP另一种通用解法分类讨论法快归快写起来容易漏情况。我还实现了一版数位DP做交叉验证顺便应对将来可能出现的复杂约束比如统计区间[l, r]内所有数字0和1的个数带上下界限制。数位DP的核心是记忆化搜索。状态设计为(pos, cnt, started, limit)pos表示当前处理到第几位cnt表示前面已经出现了多少个目标数字started表示是否已经遇到过非零数字用来处理前导零limit表示当前位是否受到原数字上限约束。from functools import lru_cache def count_zero_one_in_range(n): digits list(map(int, str(n))) lru_cache(maxsizeNone) def dfs(pos, cnt, started, limit, target): if pos len(digits): return cnt max_digit digits[pos] if limit else 9 total 0 for d in range(max_digit 1): next_started started or d ! 0 add 0 if next_started and d target: add 1 total dfs(pos 1, cnt add, next_started, limit and d max_digit, target) return total zero_count dfs(0, 0, False, True, 0) one_count dfs(0, 0, False, True, 1) return zero_count, one_count这段代码统计数字0和数字1的出现次数。关键在add那一步只有已经started且当前位等于target时才计数这个条件同时排除了前导零也保证了数字0内部的0位能被正常统计。比如数字100在统计0时百位1不是0不计十位0计入个位0计入所以100贡献2个0而数字5没有started直接结束不产生任何统计这正好排除了前导零。数位DP比分类讨论法慢一点但胜在通用且不易错尤其适合统计目标数字0时避免搞错前导零。我最后线上用的方案是分类讨论法跑生产数据数位DP放在测试代码里做交叉验证。5. 性能实测与数据对比5.1 测试环境与基准方法整个项目做完后我整理了一轮实测。测试环境是笔记本上的Python 3.11和C17CPU是Intel i5-1240P内存16GB。测试数据分为三组随机生成的100万个32位整数、区间[0, 10^6]的二进制1总数统计、区间[1, 10^6]的十进制0和1出现次数统计。为了保证公平我统一用time.perf_counter计时每个方案跑3次取最小值Python的__builtin_popcount测试用C的std::chrono计时。5.2 单点统计方案对比对100万个随机整数统计每个数的二进制1个数结果如下方案耗时(Python)说明逐位检查法3.42秒每数平均循环16次分支预测不友好Kernighan算法1.95秒循环次数取决于1的个数随机数平均约16次略快8位查表法0.82秒固定4次查表无循环分支速度优势明显内置popcount0.05秒(C)映射到CPU指令硬件加速碾压所有纯软件方案查表法相较Kernighan提升约2.4倍原因是消除了循环分支。现代CPU的分支预测面对随机数据时命中率不稳定查表法则完全避开了这个问题。5.3 区间统计方案对比对[0, 10^6]内所有整数统计二进制1的总数按位统计法耗时0.2毫秒递归法耗时0.3毫秒而逐个数调用Kernighan再累加的直觉方案耗时约2秒。这个差距是四个数量级在实际工程里意味着是否能做成实时接口的差别。十进制数位统计方面对[1, 10^6]统计0和1出现次数分类讨论法耗时0.5毫秒数位DP耗时1.2毫秒暴力字符串统计耗时超过5秒。分类讨论法是目前综合最优解。5.4 语言层面的实际差异同样的算法我用Python和C都写了一遍观察到的差异很有代表性。Python的整数是任意精度的处理超大数时不需要担心溢出这很省心但Python每条字节码开销高循环内任何多余操作都会被放大。C则反过来内置int在n超过21亿时可能溢出必须用long long或unsigned long long但是CPU指令集对位运算支持极好。最典型的例子是__builtin_popcount#include iostream int main() { unsigned int x 123456789; std::cout __builtin_popcount(x) std::endl; return 0; }这个函数在支持POPCNT指令的CPU上编译后直接翻译成一条汇编指令比任何手写循环都快。前提是确认目标运行环境的CPU支持该指令否则需要回退到查表法。我的经验是线上生产环境跑位运算密集型任务优先用C或Rust这类能直接映射到硬件指令的语言如果只能写Python就老老实实用查表法。6. 常见问题与排查技巧实录6.1 Kernighan算法遇到负数为什么异常我在初版代码里直接对负数调用了Kernighan算法发现循环次数对不上。原因是Python和C处理负数的方式不同Python的整数是无限精度负数右移时高位补1导致n (n - 1)永远消不完最左侧的1C的负数右移依赖实现有些编译器是算术右移同样补1。处理方法是先统一转成无符号视角。C里可以用unsigned intPython里可以通过n 0xffffffff把负数转成等价的无符号32位表示再走位运算。6.2 十进制统计0时为什么总差1个最典型的问题是统计[1, N]时0的个数代码跑出来总是比暴力验证多1。原因有两个一是把0这个数本身也统计进去了数字0的十进制写法只有一个0位如果不排除在统计范围[1, N]时会凭空多出1个0。二是前导零处理不当数字5不应该在统计0时产生任何贡献但如果不维护started状态5会由于“第0位是0”被误计一次。我最后统一口径统计范围是[1, N]统计目标0统计规则不计算前导零只计算数字在自然写法下出现的字符0。6.3 数位DP递归爆栈数位DP用Python写成递归版本N达到10^18时递归层数是18层本身不会爆栈真正爆栈的情况是状态没有记忆化。如果漏写lru_cache(maxsizeNone)搜索树会指数级膨胀先是超时接着是递归超过Python默认的1000层限制。排查方法很简单在dfs函数里加一个计数器如果调用次数超过1万次基本可以断定缓存没生效。6.4 边界测试用例参考每次改完算法我都跑一套固定的边界用例包含0、1、2、3、9、10、11、99、100、101、213、999、1000这几个数字。针对二进制统计另加2的幂次附近的值比如255、256、511、512、1023、1024。这些值能覆盖最高位进位、全9进位、0边界等最容易出错的地方。6.5 不要盲目优化整个项目里最深刻的体会之一是单点统计再快如果用错场景也白搭。比如查表法很快但如果只是统计几百个数的1个数直接用Python内置的bin(n).count(1)就完事了可读性最好只有数据量到了百万级再上查表法。Kernighan算法在稀疏数据上表现好在数据稠密时反而不如查表法稳定。选择算法的依据应该是数据的1密度分布。数据稀疏用Kernighan数据未知就用查表法兜底。这类“看数据选算法”的经验比背下所有最优解重要得多。7. 从这轮实践中沉淀下来的思考做完这个“0和1的个数”项目最大的收获不是掌握了某个具体公式而是建立了一套针对数位统计问题的排查思路先确认统计口径再手推小样本接着写暴力程序交叉验证最后才是性能优化。以后再遇到类似的需求比如统计某个大区间内数字3和7的出现次数或者统计自定义基数下的0和1分布我会直接采用这套组合方案分类讨论法处理常规场景数位DP处理复杂约束查表法处理海量单点统计两套独立实现互相验证。最后分享一个小技巧任何数位统计代码写完第一时间跑一下N213这个用例它覆盖了几乎所有边界分支只要这个值能对上代码基本就不会有大的结构性问题。