企业官网建设流程全解析

接到这个“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，二进制是1100，n - 1 = 1011，两者做与运算得到1000，也就是8，最右侧的1被清掉了。再来一轮，n = 8，n - 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^(k+1)为周期的。在每个周期里，前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,101，1的个数分别为0,1,1,2,1,2，总和是7。

用按位统计法：第0位周期为2，6个数有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。最终3+2+2=7。正确。

这个方案的时间复杂度是O(logN)，N就算到10^18也能秒出结果。对比之前N=1亿要跑两分钟，现在几乎瞬间完成，这才是工程上能用的方案。

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这几个值，手算出结果后跑程序对比。

N=0 -> 二进制0，1总数0 N=1 -> 0,1 总数1 N=2 -> 0,1,10 总数2 N=3 -> 0,1,10,11 总数4 N=7 -> 0到7二进制000到111，总和12 N=8 -> 加上1000，总和13 N=15 -> 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^(k+1)，而十进制里每一位的周期是10^(k+1)，但处理当前位数字是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个数里十位为0，210到213的十位为1，但这14个数里十位为1的其实是210、211、212、213这4个，这里十位上的1出现了4次。两部分相加，十位上1的总数是24。

如果把规则抽象成公式：设当前位权重是pow = 10^k，更高位数值为higher，更低位数值为lower，当前位数字是cur。那么当前位上1出现的次数分为三种情况：

• cur = 0时，次数 = higher × pow
• cur = 1时，次数 = higher × pow + lower + 1
• cur > 1时，次数 = (higher + 1) × pow

对N = 213验证一下：个位pow=1，cur=3，higher=21，次数=(21+1)×1=22，也就是数字1、11、21、31...201、211这些个位为1的情况，共21+1=22个，正确；十位pow=10，cur=1，higher=2，lower=3，次数=2×10+3+1=24，和上面手算一致；百位pow=100，cur=2，higher=0，次数=(0+1)×100=100，也就是100到199这100个数字的百位都是1，正确。总和22+24+100=146。

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 count

4.3 数字0的出现次数：前导零是最大的坑

数字1统计完成后，我天真地以为把公式里的1换成0就行，结果跑出来N=213时数字0的出现次数是42，但手工验证明显不对。问题出在：如果完全套用统计1的公式去统计0，会把数字写成定长格式时高位补的那些前导零也统计进去。

让我重新推。统计0的时候不能把最高位之前的前导零算进去，因为数字0不是一个有意义的前导位。更稳的做法是：换个角度，统计[1, N]之间所有十进制数字的长度总和，减去除了0以外的所有数字（即1到9的出现次数），剩下的就是0的出现次数。

数字1到9的出现次数可以继续用分类讨论法逐个统计。以数字d（d从1到9）为例，当前位cur分三种情况：cur < d，次数 = higher × pow；cur = d，次数 = higher × pow + lower + 1；cur > 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次，非零总数146+320=466，但数字总位数是531，这就有问题了，因为总位数包含的是所有位，而非零数字出现次数加上零出现次数正好等于所有位上的数字出现次数合计数。重新理清口径：总位数531，非零数字总出现次数应该等于531减去0的出现次数。如果0出现42次，则非零出现489次。写程序确认后，数字0在N=213里确实出现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(maxsize=None) 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和C++17，CPU是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个数，结果如下：

查表法相较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)永远消不完最左侧的1；C++的负数右移依赖实现，有些编译器是算术右移同样补1。

处理方法是先统一转成无符号视角。C++里可以用unsigned int，Python里可以通过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(maxsize=None)，搜索树会指数级膨胀，先是超时，接着是递归超过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处理复杂约束，查表法处理海量单点统计，两套独立实现互相验证。最后分享一个小技巧：任何数位统计代码写完，第一时间跑一下N=213这个用例，它覆盖了几乎所有边界分支，只要这个值能对上，代码基本就不会有大的结构性问题。