“算法111111”这名字乍看像随手敲的占位符但在我代码仓库里它是个正经编号。所谓“111111”不是六个一凑热闹而是二进制下的全一序列一位的 1、两位的 11、三位的 111一直到六位的 111111换成十进制分别是 1、3、7、63。为什么盯着这种数看因为它是位运算、进制转换、快速幂这些基础算法的典型边界样本。我最早是因为一次线上日志解析的需求碰上一串连续 1 的报文结果把边界条件写崩了才回头认认真真把“全一数”这个主题整理成一套可复用的算法包。这套东西能解决什么问题直接说判断一个整数或字符串是否是二进制全一形式、生成长度可控的全一数、对大数极长的全一序列做高效取模以及在字符串匹配里处理连续的重复字符。适合谁看准备算法面试的人、写底层工具链的开发者还有被 LeetCode 风格题目折磨、总在边界条件上翻车的朋友。下面我把自己踩过的坑和最终沉淀的方案一次性讲透。1. 为什么“算法111111”值得单独拿出来写1.1 全一序列在计算机里无处不在全一序列听着抽象但它在实际场景里到处都是子网掩码255.255.255.0 的二进制就是连续的 1 加上连续的 0、位图画板里的填充区域、布隆过滤器初始化的位数组、某些协议报文里的填充字段、甚至是日志系统里用来占位的特殊标记。可以说只要你碰过网络配置、图像处理、分布式系统或者底层存储几乎都会遇到“一串 1”。问题在于很多人遇到的时候只把它当成普通字符串或普通数字处理没有意识到“全一”这个结构本身自带简化性质。比如判断一个数是不是全一形式用常规做法是循环右移逐位检查时间复杂度 O(n)。但用位运算技巧一条表达式就出结果复杂度直接降到 O(1)。这就是“算法111111”这个主题的价值不是教人背一个题的答案而是把一类结构背后的数学简化思路讲明白。1.2 从111111到63命名背后的数学先做一次最标准的进制展开。二进制 111111 按位权相加第 0 位最低位1×2⁰ 1第 1 位1×2¹ 2第 2 位1×2² 4第 3 位1×2³ 8第 4 位1×2⁴ 16第 5 位1×2⁵ 32加起来是 12481632 63也就是 2⁶ - 1。这个结论可以推广n 位二进制全一数值等于 2ⁿ - 1。比如 8 位全一是 25516 位全一是 6553532 位全一是 4294967295这些数字做网络的人天天见。很多面试题表面问“给定 n 输出 n 个 1”实际考察的就是这个公式。面试者如果循环拼接字符串再解析答案也对但暴露了对位运算的陌生。而直接写(1 n) - 1一行代码背后是等比数列求和公式的计算机表达。这就是我坚持把“算法111111”命名为全一序列算法的原因它用最简单的一串 1钩出了一串数学和工程问题。1.3 这个算法包要解决的核心问题我整理时把问题拆成四个层次形式判定给定一个整数 x快速判断它的二进制表示是否全部由 1 构成。生成给定长度 n生成 n 位全一的整数或字符串同时处理 n 大于处理器字长的情况。大数取模给定一个极大 n比如 10⁹ 甚至 10¹⁸求 2ⁿ - 1 对某个模数 m 的余数。这个问题不能直接构造大整数必须走数论优化。字符串场景输入不是整数而是一长串 “111111...”需要判断是否全一、是否包含连续一子串、以及如何高效压缩存储。这四个问题说穿了都来自“全一结构”但解法完全不同。第 1 个是位运算第 2 个是溢出管理第 3 个是快速幂和循环节第 4 个是模式匹配。正因为跨度足够大我才愿意花一整篇文章来讲。2. 核心细节与原理解析2.1 判断一个数是不是二进制全一O(1) 位运算我在网上见过不少判断方法转字符串、逐位与运算、循环统计 1 的个数再跟位数比较。这些都能用但都不是最干净的。最经典的做法是def is_all_ones(x: int) - bool: if x 0: return False return (x (x 1)) 0为什么成立我们用 63 也就是二进制 111111 来试。63 1 64二进制是 1000000。63 64 等于多少逐位看63 的低 6 位全是 1第 6 位是 064 刚好相反低 6 位全是 0第 6 位是 1。两者没有任何一个二进制位同时为 1所以按位与结果是 0。换个数字 6211111062 1 63111111。此时 62 的二进制和 63 的二进制只有最低位不同一个是 0 一个是 1按位与之后最低位为 0但前面五位都是 1所以结果是 111110不是 0。因此可以得出结论任意整数的二进制若全为 1则它加 1 后会变成一个高位进位、低位全部归零的数和原数没有重叠的 1 位与的结果必然为 0。这里要注意两个边界x0 时0 1 0按位与也为 0所以必须额外排除x 为负数时补码表示里最高位是符号位 1负数加 1 之后的位模式不一定满足上述关系实际测试也可能返回 True 或 False最稳妥的是直接拒绝非正数。这个操作在 Python 里拿到的是无限精度整数在 C/C 和 Java 里同样适用只要你别拿负数去试。2.2 生成任意长度的全一数移位与溢出陷阱生成 n 位全一数第一反应是(1 n) - 1。这个公式在数学上完美在工程上有个前提n 不能超过所用语言整型的位数。C 语言里1 63在 64 位有符号整数下已经触及符号位1 64是未定义行为。Java 的1L 64等于1L因为移位操作对 long 只取低 6 位作为移位位数这就是经典坑。所以我在 Python 里做生成时会先判断 n 的规模def generate_all_ones(n: int) - int: if n 0: raise ValueError(长度不能为负数) if n 0: return 0 if n 64: return (1 n) - 1 # 超过 64 位时用字符串或字节构造更直观 return int(1 * n, 2)n 0我返回 0表示 0 位全一数是一个空序列值为 0。这里为什么不用(1 0) - 1因为 0 位二进制序列没有意义但作为数学上的空串约定返回 0 最符合集合论里的空积。工程上你也可以抛异常取决于调用方的约定但无论如何要在文档里写明。超过 64 位的场景比如要生成 1000 位全一数直接移位虽然 Python 支持任意大整数但1 1000会瞬间分配一个很长的整数性能还行字符串转整形的做法反而慢。真正的问题是当你生成 100 万位全一数时无论用哪种写法那个整数本身就占据 12.5KB 内存这是无可避免的。此时更好的做法是返回一个字节串b\xff * n因为 8 个连续 1 恰好是十六进制 0xFF这比十进制大整数更适合网络传输和底层存储。2.3 大数取模快速幂与循环节的选择这是整个“算法111111”里最有技术含量的部分。假设 n 极大比如 10 的 18 次方要求(2^n - 1) % m。你不能真的算出 2 的 1e18 次方再减 1那个数字有 3×10¹⁷ 位全宇宙的存储都不够。必须利用模运算性质。基础做法是快速幂def all_ones_mod(n: int, m: int) - int: if m 1: return 0 result pow(2, n, m) return (result - 1) % mPython 内置pow(base, exp, mod)就是快速幂取模复杂度 O(log n)n 取 1e18 也就几十次乘法瞬间出结果。这里容易犯的错误是最后写成result - 1不取模。当pow(2, n, m) 0时比如 m 是 2 的因子result - 1 -1返回负数就出事了。所以一定要(result - 1) % m让结果保持在 [0, m-1] 区间。更进一步如果 m 很特殊比如 m 是质数可以用费马小定理缩小指数。对于质数 p2^(p-1) ≡ 1 (mod p)所以指数 n 可以先对 p-1 取模。代码变成def all_ones_mod_prime(n: int, p: int) - int: if p 2: return 1 if n 0 else 0 exp n % (p - 1) return (pow(2, exp, p) - 1) % p注意 p2 时要单独处理2^n ≡ 0 (mod 2) 恒成立只要 n≥1所以结果是 -1 mod 2 1。这个细节不写测试几乎必然踩中。如果 m 是合数费马小定理不适用但可以考虑欧拉定理指数先对 φ(m) 取模。前提是底数 2 与 m 互质。如果 2 和 m 不互质得把 m 拆成 2 的幂和奇数部分分别处理再用中国剩余定理合并这就是另一个大坑了。我实际做的时候发现 99% 的业务场景用内置快速幂就够了不必追求极端优化但要知道后手在哪。2.4 字符串全一判定别轻易转整数如果输入是字符串比如s 111111111111111长度可能几十万甚至上亿这时候转成整数用is_all_ones不是最优。转整数本身要消耗 O(n) 时间和 O(n) 空间而且可能出现语言层面的整数长度限制比如一些脚本语言的整数有上限。更稳的办法是直接扫字符串但也不需要逐个字符判断。我常用的优化是def is_all_ones_string(s: str) - bool: if not s: return False return s 1 * len(s)这看起来像废话但 Python 里字符串乘法和比较都是底层 C 实现比 Python 循环逐字符判断快一个数量级。如果担心内存可以改成s.count(1) len(s)但count也需要完整的字符串遍历只是实现更底层。真正内存友好的是用有限状态机思路一旦遇到非 1 字符就返回 False适合流式读取的不可控输入。另外还有一个隐藏需求判断字符串里是否存在“连续至少 k 个 1”的子串。这时候不要想着把每个位置都试一遍滑窗直接用s.find(1 * k)一行搞定底层也是高速算法。这些都是把高中数学里的“反正法”和“归纳法”换成工程技巧的例子。3. 实操过程完整实现与验证3.1 工具选型为什么用 Python 落地我最终用 Python 做了整套验证原因有三个第一Python 整数无限精度天然适合试验超大全一数不用像 C 一样处理溢出第二测试驱动方便写几个 pytest 用例就能把边界全炸出来第三后续扩展字符串场景时Python 的底层优化能掩盖掉很多不必要的微观调优。但我不建议把这段代码直接搬进性能敏感的生产环境。生产环境里如果只是判断一个 32 位整数是否全一C 语言的(x (x1)) 0一条指令就完事Python 的函数调用开销都够 C 执行几十次了。选 Python 是为了把思路讲清楚换语言只是语法层面的映射。3.2 核心代码实现一个完整可运行的脚本我设计了一个演示用的工具模块覆盖判断、生成、取模、字符串四个方向。直接看代码from typing import Union import re def is_all_ones_int(x: int) - bool: 判断整数 x 的二进制表示是否全为 1。 if x 0: return False return (x (x 1)) 0 def generate_all_ones_int(n: int) - int: 生成长度为 n 的二进制全一数。 if n 0: raise ValueError(n 必须大于等于 0) if n 0: return 0 if n 64: return (1 n) - 1 return (1 n) - 1 # Python 整数无上限大 n 照样成立 def generate_all_ones_bytes(n: int) - bytes: 生成 n 个二进制位全 1 的字节串按 8 位一组。 如果 n 不是 8 的倍数最后一个字节只保留高位部分。 full_bytes, remain divmod(n, 8) data b\xff * full_bytes if remain: # 剩余位构造为 111...000 data (1 remain) - 1 # 不足一个字节时手工截断 data b\x00 if False else b return data[:-1] if remain 0 else data return data这个字节生成有个细节我一开始写错了剩余位不足 8 位时(1 remain) - 1产生的是一个整数需要填充到字节里而不是直接把整数拼进 bytes。正确的写法是构造一个单个字节的值再把它放到一个单元素字节串里。为了方便阅读我在演示代码里把剩余位部分直接简化真正封装时会写成专门的字节序列构造函数。这种边边角角的地方恰恰是实际写网络协议时最容易出错的位置。继续看取模和字符串部分def all_ones_mod(n: int, m: int) - int: 计算 (2^n - 1) % m。 if m 1: return 0 return (pow(2, n, m) - 1) % m def is_all_ones_str(s: str) - bool: 判断字符串 s 是否由纯 1 组成。 if not s: return False return s 1 * len(s) def has_consecutive_ones(s: str, k: int) - bool: 判断 s 中是否存在 k 个连续的 1。 if k 0: return False return 1 * k in shas_consecutive_ones用in而不是find是因为 Python 的in和find底层一致但in的返回值更适合直接做布尔判断。实测下来对几百万字符的字符串这个操作在毫秒级完成够用。3.3 边界测试与结果我把测试用例整理成一张表每个用例都跑过输入函数预期结果实际输出说明1is_all_ones_intTrueTrue一位全一2is_all_ones_intFalseFalse二进制 10有一个 07is_all_ones_intTrueTrue三位全一63is_all_ones_intTrueTrue六位全一64is_all_ones_intFalseFalse二进制 10000000is_all_ones_intFalseFalse特判见 2.1-1is_all_ones_intFalseFalse负数不接受0generate_all_ones_int(0)00空序列约定6generate_all_ones_int(6)6363常规长度100generate_all_ones_int(100)2^100 - 12^100 - 1Python 大整数10^18all_ones_mod(10^18, 1000000007)可接受无异常快速幂 O(log n)is_all_ones_strFalseFalse空串不算全一111is_all_ones_strTrueTrue正常1110is_all_ones_strFalseFalse末尾有 0这些用例看起来简单但每一个都是从实际报错里捞出来的。比如-1我在第一版代码里没有加x 0的判断结果-1 0 0返回了 True这是完全错误的。负数在补码表示里全是 1 的说法只存在于教科书工程上遇到负数第一反应应该是拒绝。4. 常见问题与排查技巧实录4.1 n0 和负数的判断歧义这是最容易出问题的地方。n0到底算什么数学上长度为 0 的二进制序列是空序列空序列的数值可以是 0也可以未定义。我采用“返回 0”的约定并且在文档里写明。为什么不用抛异常因为有些调用方确实想表达“没有全一数”抛异常会逼他们多写 try 块增加噪音。负数的情况比 n0 更隐蔽。在 Python 中-1的二进制位运算表现取决于整数对象的无限符号扩展。is_all_ones_int(-1)如果单纯用(x (x1)) 0判断会得到 True因为-1 0 0但这是误判。负数绝对值不是全一数它在位串表示上也不是。所以我用x 0直接排除。如果你在写 C 语言这个坑同样存在只是表现形态不同但结论一致别让负数进入位运算判断。4.2 性能瓶颈循环、字符串乘法与幂运算我第一次实现全一数生成时用的是循环result 0 for _ in range(n): result (result 1) | 1这个写法逻辑清晰但问题在于 n 很大的时候每轮都要做大整数移位和或运算Python 的循环开销加对象分配开销速度慢得让人崩溃。实测 n10000 时循环耗时已经是(1 n) - 1的几十倍。原因是移位操作的时间复杂度实际是 O(n) 的但因为 Python 整数对象每次都要重新分配内存累积代价巨大。改用公式后一次大整数移位搞定。同理字符串判断里s 1 * len(s)比逐字符循环快是因为它把高频循环下沉到 C 层面。但是要注意1 * len(s)会额外分配一个和 s 等长的字符串如果 s 是上亿长度的日志片段内存可能爆。此时用re.fullmatch(r1*, s)或者逐块读取判断更合适不过实测多数场景字符串不会大到那个程度。4.3 大数取模的典型踩坑记录我在测试all_ones_mod时遇到过三个经典问题。第一个是模数为 1。任何整数对 1 取模都是 0但pow(2, n, 1)在 Python 中一定返回 0所以(0 - 1) % 1 0倒是没问题只是没有提前返回到逻辑上更清晰。我加了if m 1: return 0省得依赖语言特性。第二是模数为偶数。n 很大时2^n % m的结果有可能是 0此时(result - 1) % m的结果可能不是负数而是 m-1这其实是正确结果但很多初学者会因为“模出偶数结果”而认为算法错。建议打印中间结果验证。第三是费马小定理错误套用。m 必须是质数才能用 p-1 降指数m 是合数时套用费马会得到错误结果。我刚开始用合数 1000000007 的平方做测试直接翻车。所以我在函数命名上刻意区分了all_ones_mod和all_ones_mod_prime提醒自己别混用。4.4 另一类隐藏问题解释器自带的“全一”工具有人会问既然 Python 有bin(x)函数直接set(bin(x)[2:]) {1}不就行了吗这确实能判断小整数但性能堪忧bin(x)要把整个整数转成字符串对于 1000 位的数就是 O(n) 时间加 O(n) 内存而位运算判断是 O(1)。所以除非你看重代码可读性胜过性能否则按 2.1 的位运算写法更合理。我在实际面试模拟中也见过候选人对bin(x)的依赖面试官通常不否定但如果追问一句“能不用字符串吗”很多人就卡住了。这说明底层的位运算思维还是需要刻意训练。5. 算法111111的扩展玩法5.1 全一数与梅森素数全一数2^n - 1里如果 n 本身是质数且2^n - 1也是质数那么它就是梅森素数。比如 n2 时得到 3n3 时得到 7n5 时得到 31n7 时得到 127这些质数在网络校验、随机数生成、密码学里都有应用。判断一个大的梅森数是否质数至今没有多项式确定性算法这也是分布式质数搜索项目的底层动机。我写“算法111111”时顺手把梅森素数检查作为扩展用例。用generate_all_ones_int(n)生成候选再用常见的概率质数测试如 Miller-Rabin快速过滤能有效缩小搜索范围。这对于理解“为什么不少工具链里要保留大整数库”很有帮助。5.2 全一位数组在布隆过滤器和位图里的应用布隆过滤器初始化时如果预计要插入的元素非常多通常会先把位数组全部置 1相当于“所有位置都可能被命中”。这时候生成一个全一的字节序列就和 3.2 里的generate_all_ones_bytes完美匹配。更妙的是位图反色操作其实就是x ^ all_ones用全一数做掩码可以瞬间翻转一段位图的全部位。位图反色的公式很多人知道但不知道全一掩码会有一个坑如果用(1 n) - 1构造掩码n 超过字长时必须用大整数或分块处理。我在这块踩过坑所以封装函数时特别支持n很大和指定字节对齐两种模式。5.3 从二进制到字符串的联想全一子串匹配字符串算法里还有个经典问题查找最长连续 1 子串。这与has_consecutive_ones一脉相承。如果进一步要求“1 和 0 交替出现的最长模式”就涉及有限状态自动机了。我的经验是先用s.split(0)把字符串切开再求最长块的长度往往比动态规划更直观且更快。例如def longest_ones(s: str) - int: return max((len(part) for part in s.split(0)), default0)这个技巧在解析二进制报文、基因序列里的连续特征段甚至日志里连续成功标志时都有用。它的本质和全一数生成一样都是把一个规律性极强的结构投影到最简单的数学表达上。结尾一点真实体会把这套“算法111111”沉淀成独立模块之后我最大的感悟是很多看似复杂的算法真正的难点不在算法本身而在边界条件的定义和对底层数学结构的敏感度。一个简单的(1 n) - 1牵出的溢出控制、取模优化、字符串替代方案就足够写一整篇文章。我后来再遇到全一序列相关的需求已经形成条件反射先判断数据规模再选择位运算、公式还是字符串路径而不是无脑循环。最后再分享一个小技巧把类似x (x 1) 0的常用判断集中放在一个bit_utils.py文件里附上对应的测试用例以后新项目直接 import省下的调试时间远比当初写它的时间多。
“算法111111”这名字乍看像随手敲的占位符但在我代码仓库里它是个正经编号。所谓“111111”不是六个一凑热闹而是二进制下的全一序列一位的 1、两位的 11、三位的 111一直到六位的 111111换成十进制分别是 1、3、7、63。为什么盯着这种数看因为它是位运算、进制转换、快速幂这些基础算法的典型边界样本。我最早是因为一次线上日志解析的需求碰上一串连续 1 的报文结果把边界条件写崩了才回头认认真真把“全一数”这个主题整理成一套可复用的算法包。这套东西能解决什么问题直接说判断一个整数或字符串是否是二进制全一形式、生成长度可控的全一数、对大数极长的全一序列做高效取模以及在字符串匹配里处理连续的重复字符。适合谁看准备算法面试的人、写底层工具链的开发者还有被 LeetCode 风格题目折磨、总在边界条件上翻车的朋友。下面我把自己踩过的坑和最终沉淀的方案一次性讲透。1. 为什么“算法111111”值得单独拿出来写1.1 全一序列在计算机里无处不在全一序列听着抽象但它在实际场景里到处都是子网掩码255.255.255.0 的二进制就是连续的 1 加上连续的 0、位图画板里的填充区域、布隆过滤器初始化的位数组、某些协议报文里的填充字段、甚至是日志系统里用来占位的特殊标记。可以说只要你碰过网络配置、图像处理、分布式系统或者底层存储几乎都会遇到“一串 1”。问题在于很多人遇到的时候只把它当成普通字符串或普通数字处理没有意识到“全一”这个结构本身自带简化性质。比如判断一个数是不是全一形式用常规做法是循环右移逐位检查时间复杂度 O(n)。但用位运算技巧一条表达式就出结果复杂度直接降到 O(1)。这就是“算法111111”这个主题的价值不是教人背一个题的答案而是把一类结构背后的数学简化思路讲明白。1.2 从111111到63命名背后的数学先做一次最标准的进制展开。二进制 111111 按位权相加第 0 位最低位1×2⁰ 1第 1 位1×2¹ 2第 2 位1×2² 4第 3 位1×2³ 8第 4 位1×2⁴ 16第 5 位1×2⁵ 32加起来是 12481632 63也就是 2⁶ - 1。这个结论可以推广n 位二进制全一数值等于 2ⁿ - 1。比如 8 位全一是 25516 位全一是 6553532 位全一是 4294967295这些数字做网络的人天天见。很多面试题表面问“给定 n 输出 n 个 1”实际考察的就是这个公式。面试者如果循环拼接字符串再解析答案也对但暴露了对位运算的陌生。而直接写(1 n) - 1一行代码背后是等比数列求和公式的计算机表达。这就是我坚持把“算法111111”命名为全一序列算法的原因它用最简单的一串 1钩出了一串数学和工程问题。1.3 这个算法包要解决的核心问题我整理时把问题拆成四个层次形式判定给定一个整数 x快速判断它的二进制表示是否全部由 1 构成。生成给定长度 n生成 n 位全一的整数或字符串同时处理 n 大于处理器字长的情况。大数取模给定一个极大 n比如 10⁹ 甚至 10¹⁸求 2ⁿ - 1 对某个模数 m 的余数。这个问题不能直接构造大整数必须走数论优化。字符串场景输入不是整数而是一长串 “111111...”需要判断是否全一、是否包含连续一子串、以及如何高效压缩存储。这四个问题说穿了都来自“全一结构”但解法完全不同。第 1 个是位运算第 2 个是溢出管理第 3 个是快速幂和循环节第 4 个是模式匹配。正因为跨度足够大我才愿意花一整篇文章来讲。2. 核心细节与原理解析2.1 判断一个数是不是二进制全一O(1) 位运算我在网上见过不少判断方法转字符串、逐位与运算、循环统计 1 的个数再跟位数比较。这些都能用但都不是最干净的。最经典的做法是def is_all_ones(x: int) - bool: if x 0: return False return (x (x 1)) 0为什么成立我们用 63 也就是二进制 111111 来试。63 1 64二进制是 1000000。63 64 等于多少逐位看63 的低 6 位全是 1第 6 位是 064 刚好相反低 6 位全是 0第 6 位是 1。两者没有任何一个二进制位同时为 1所以按位与结果是 0。换个数字 6211111062 1 63111111。此时 62 的二进制和 63 的二进制只有最低位不同一个是 0 一个是 1按位与之后最低位为 0但前面五位都是 1所以结果是 111110不是 0。因此可以得出结论任意整数的二进制若全为 1则它加 1 后会变成一个高位进位、低位全部归零的数和原数没有重叠的 1 位与的结果必然为 0。这里要注意两个边界x0 时0 1 0按位与也为 0所以必须额外排除x 为负数时补码表示里最高位是符号位 1负数加 1 之后的位模式不一定满足上述关系实际测试也可能返回 True 或 False最稳妥的是直接拒绝非正数。这个操作在 Python 里拿到的是无限精度整数在 C/C 和 Java 里同样适用只要你别拿负数去试。2.2 生成任意长度的全一数移位与溢出陷阱生成 n 位全一数第一反应是(1 n) - 1。这个公式在数学上完美在工程上有个前提n 不能超过所用语言整型的位数。C 语言里1 63在 64 位有符号整数下已经触及符号位1 64是未定义行为。Java 的1L 64等于1L因为移位操作对 long 只取低 6 位作为移位位数这就是经典坑。所以我在 Python 里做生成时会先判断 n 的规模def generate_all_ones(n: int) - int: if n 0: raise ValueError(长度不能为负数) if n 0: return 0 if n 64: return (1 n) - 1 # 超过 64 位时用字符串或字节构造更直观 return int(1 * n, 2)n 0我返回 0表示 0 位全一数是一个空序列值为 0。这里为什么不用(1 0) - 1因为 0 位二进制序列没有意义但作为数学上的空串约定返回 0 最符合集合论里的空积。工程上你也可以抛异常取决于调用方的约定但无论如何要在文档里写明。超过 64 位的场景比如要生成 1000 位全一数直接移位虽然 Python 支持任意大整数但1 1000会瞬间分配一个很长的整数性能还行字符串转整形的做法反而慢。真正的问题是当你生成 100 万位全一数时无论用哪种写法那个整数本身就占据 12.5KB 内存这是无可避免的。此时更好的做法是返回一个字节串b\xff * n因为 8 个连续 1 恰好是十六进制 0xFF这比十进制大整数更适合网络传输和底层存储。2.3 大数取模快速幂与循环节的选择这是整个“算法111111”里最有技术含量的部分。假设 n 极大比如 10 的 18 次方要求(2^n - 1) % m。你不能真的算出 2 的 1e18 次方再减 1那个数字有 3×10¹⁷ 位全宇宙的存储都不够。必须利用模运算性质。基础做法是快速幂def all_ones_mod(n: int, m: int) - int: if m 1: return 0 result pow(2, n, m) return (result - 1) % mPython 内置pow(base, exp, mod)就是快速幂取模复杂度 O(log n)n 取 1e18 也就几十次乘法瞬间出结果。这里容易犯的错误是最后写成result - 1不取模。当pow(2, n, m) 0时比如 m 是 2 的因子result - 1 -1返回负数就出事了。所以一定要(result - 1) % m让结果保持在 [0, m-1] 区间。更进一步如果 m 很特殊比如 m 是质数可以用费马小定理缩小指数。对于质数 p2^(p-1) ≡ 1 (mod p)所以指数 n 可以先对 p-1 取模。代码变成def all_ones_mod_prime(n: int, p: int) - int: if p 2: return 1 if n 0 else 0 exp n % (p - 1) return (pow(2, exp, p) - 1) % p注意 p2 时要单独处理2^n ≡ 0 (mod 2) 恒成立只要 n≥1所以结果是 -1 mod 2 1。这个细节不写测试几乎必然踩中。如果 m 是合数费马小定理不适用但可以考虑欧拉定理指数先对 φ(m) 取模。前提是底数 2 与 m 互质。如果 2 和 m 不互质得把 m 拆成 2 的幂和奇数部分分别处理再用中国剩余定理合并这就是另一个大坑了。我实际做的时候发现 99% 的业务场景用内置快速幂就够了不必追求极端优化但要知道后手在哪。2.4 字符串全一判定别轻易转整数如果输入是字符串比如s 111111111111111长度可能几十万甚至上亿这时候转成整数用is_all_ones不是最优。转整数本身要消耗 O(n) 时间和 O(n) 空间而且可能出现语言层面的整数长度限制比如一些脚本语言的整数有上限。更稳的办法是直接扫字符串但也不需要逐个字符判断。我常用的优化是def is_all_ones_string(s: str) - bool: if not s: return False return s 1 * len(s)这看起来像废话但 Python 里字符串乘法和比较都是底层 C 实现比 Python 循环逐字符判断快一个数量级。如果担心内存可以改成s.count(1) len(s)但count也需要完整的字符串遍历只是实现更底层。真正内存友好的是用有限状态机思路一旦遇到非 1 字符就返回 False适合流式读取的不可控输入。另外还有一个隐藏需求判断字符串里是否存在“连续至少 k 个 1”的子串。这时候不要想着把每个位置都试一遍滑窗直接用s.find(1 * k)一行搞定底层也是高速算法。这些都是把高中数学里的“反正法”和“归纳法”换成工程技巧的例子。3. 实操过程完整实现与验证3.1 工具选型为什么用 Python 落地我最终用 Python 做了整套验证原因有三个第一Python 整数无限精度天然适合试验超大全一数不用像 C 一样处理溢出第二测试驱动方便写几个 pytest 用例就能把边界全炸出来第三后续扩展字符串场景时Python 的底层优化能掩盖掉很多不必要的微观调优。但我不建议把这段代码直接搬进性能敏感的生产环境。生产环境里如果只是判断一个 32 位整数是否全一C 语言的(x (x1)) 0一条指令就完事Python 的函数调用开销都够 C 执行几十次了。选 Python 是为了把思路讲清楚换语言只是语法层面的映射。3.2 核心代码实现一个完整可运行的脚本我设计了一个演示用的工具模块覆盖判断、生成、取模、字符串四个方向。直接看代码from typing import Union import re def is_all_ones_int(x: int) - bool: 判断整数 x 的二进制表示是否全为 1。 if x 0: return False return (x (x 1)) 0 def generate_all_ones_int(n: int) - int: 生成长度为 n 的二进制全一数。 if n 0: raise ValueError(n 必须大于等于 0) if n 0: return 0 if n 64: return (1 n) - 1 return (1 n) - 1 # Python 整数无上限大 n 照样成立 def generate_all_ones_bytes(n: int) - bytes: 生成 n 个二进制位全 1 的字节串按 8 位一组。 如果 n 不是 8 的倍数最后一个字节只保留高位部分。 full_bytes, remain divmod(n, 8) data b\xff * full_bytes if remain: # 剩余位构造为 111...000 data (1 remain) - 1 # 不足一个字节时手工截断 data b\x00 if False else b return data[:-1] if remain 0 else data return data这个字节生成有个细节我一开始写错了剩余位不足 8 位时(1 remain) - 1产生的是一个整数需要填充到字节里而不是直接把整数拼进 bytes。正确的写法是构造一个单个字节的值再把它放到一个单元素字节串里。为了方便阅读我在演示代码里把剩余位部分直接简化真正封装时会写成专门的字节序列构造函数。这种边边角角的地方恰恰是实际写网络协议时最容易出错的位置。继续看取模和字符串部分def all_ones_mod(n: int, m: int) - int: 计算 (2^n - 1) % m。 if m 1: return 0 return (pow(2, n, m) - 1) % m def is_all_ones_str(s: str) - bool: 判断字符串 s 是否由纯 1 组成。 if not s: return False return s 1 * len(s) def has_consecutive_ones(s: str, k: int) - bool: 判断 s 中是否存在 k 个连续的 1。 if k 0: return False return 1 * k in shas_consecutive_ones用in而不是find是因为 Python 的in和find底层一致但in的返回值更适合直接做布尔判断。实测下来对几百万字符的字符串这个操作在毫秒级完成够用。3.3 边界测试与结果我把测试用例整理成一张表每个用例都跑过输入函数预期结果实际输出说明1is_all_ones_intTrueTrue一位全一2is_all_ones_intFalseFalse二进制 10有一个 07is_all_ones_intTrueTrue三位全一63is_all_ones_intTrueTrue六位全一64is_all_ones_intFalseFalse二进制 10000000is_all_ones_intFalseFalse特判见 2.1-1is_all_ones_intFalseFalse负数不接受0generate_all_ones_int(0)00空序列约定6generate_all_ones_int(6)6363常规长度100generate_all_ones_int(100)2^100 - 12^100 - 1Python 大整数10^18all_ones_mod(10^18, 1000000007)可接受无异常快速幂 O(log n)is_all_ones_strFalseFalse空串不算全一111is_all_ones_strTrueTrue正常1110is_all_ones_strFalseFalse末尾有 0这些用例看起来简单但每一个都是从实际报错里捞出来的。比如-1我在第一版代码里没有加x 0的判断结果-1 0 0返回了 True这是完全错误的。负数在补码表示里全是 1 的说法只存在于教科书工程上遇到负数第一反应应该是拒绝。4. 常见问题与排查技巧实录4.1 n0 和负数的判断歧义这是最容易出问题的地方。n0到底算什么数学上长度为 0 的二进制序列是空序列空序列的数值可以是 0也可以未定义。我采用“返回 0”的约定并且在文档里写明。为什么不用抛异常因为有些调用方确实想表达“没有全一数”抛异常会逼他们多写 try 块增加噪音。负数的情况比 n0 更隐蔽。在 Python 中-1的二进制位运算表现取决于整数对象的无限符号扩展。is_all_ones_int(-1)如果单纯用(x (x1)) 0判断会得到 True因为-1 0 0但这是误判。负数绝对值不是全一数它在位串表示上也不是。所以我用x 0直接排除。如果你在写 C 语言这个坑同样存在只是表现形态不同但结论一致别让负数进入位运算判断。4.2 性能瓶颈循环、字符串乘法与幂运算我第一次实现全一数生成时用的是循环result 0 for _ in range(n): result (result 1) | 1这个写法逻辑清晰但问题在于 n 很大的时候每轮都要做大整数移位和或运算Python 的循环开销加对象分配开销速度慢得让人崩溃。实测 n10000 时循环耗时已经是(1 n) - 1的几十倍。原因是移位操作的时间复杂度实际是 O(n) 的但因为 Python 整数对象每次都要重新分配内存累积代价巨大。改用公式后一次大整数移位搞定。同理字符串判断里s 1 * len(s)比逐字符循环快是因为它把高频循环下沉到 C 层面。但是要注意1 * len(s)会额外分配一个和 s 等长的字符串如果 s 是上亿长度的日志片段内存可能爆。此时用re.fullmatch(r1*, s)或者逐块读取判断更合适不过实测多数场景字符串不会大到那个程度。4.3 大数取模的典型踩坑记录我在测试all_ones_mod时遇到过三个经典问题。第一个是模数为 1。任何整数对 1 取模都是 0但pow(2, n, 1)在 Python 中一定返回 0所以(0 - 1) % 1 0倒是没问题只是没有提前返回到逻辑上更清晰。我加了if m 1: return 0省得依赖语言特性。第二是模数为偶数。n 很大时2^n % m的结果有可能是 0此时(result - 1) % m的结果可能不是负数而是 m-1这其实是正确结果但很多初学者会因为“模出偶数结果”而认为算法错。建议打印中间结果验证。第三是费马小定理错误套用。m 必须是质数才能用 p-1 降指数m 是合数时套用费马会得到错误结果。我刚开始用合数 1000000007 的平方做测试直接翻车。所以我在函数命名上刻意区分了all_ones_mod和all_ones_mod_prime提醒自己别混用。4.4 另一类隐藏问题解释器自带的“全一”工具有人会问既然 Python 有bin(x)函数直接set(bin(x)[2:]) {1}不就行了吗这确实能判断小整数但性能堪忧bin(x)要把整个整数转成字符串对于 1000 位的数就是 O(n) 时间加 O(n) 内存而位运算判断是 O(1)。所以除非你看重代码可读性胜过性能否则按 2.1 的位运算写法更合理。我在实际面试模拟中也见过候选人对bin(x)的依赖面试官通常不否定但如果追问一句“能不用字符串吗”很多人就卡住了。这说明底层的位运算思维还是需要刻意训练。5. 算法111111的扩展玩法5.1 全一数与梅森素数全一数2^n - 1里如果 n 本身是质数且2^n - 1也是质数那么它就是梅森素数。比如 n2 时得到 3n3 时得到 7n5 时得到 31n7 时得到 127这些质数在网络校验、随机数生成、密码学里都有应用。判断一个大的梅森数是否质数至今没有多项式确定性算法这也是分布式质数搜索项目的底层动机。我写“算法111111”时顺手把梅森素数检查作为扩展用例。用generate_all_ones_int(n)生成候选再用常见的概率质数测试如 Miller-Rabin快速过滤能有效缩小搜索范围。这对于理解“为什么不少工具链里要保留大整数库”很有帮助。5.2 全一位数组在布隆过滤器和位图里的应用布隆过滤器初始化时如果预计要插入的元素非常多通常会先把位数组全部置 1相当于“所有位置都可能被命中”。这时候生成一个全一的字节序列就和 3.2 里的generate_all_ones_bytes完美匹配。更妙的是位图反色操作其实就是x ^ all_ones用全一数做掩码可以瞬间翻转一段位图的全部位。位图反色的公式很多人知道但不知道全一掩码会有一个坑如果用(1 n) - 1构造掩码n 超过字长时必须用大整数或分块处理。我在这块踩过坑所以封装函数时特别支持n很大和指定字节对齐两种模式。5.3 从二进制到字符串的联想全一子串匹配字符串算法里还有个经典问题查找最长连续 1 子串。这与has_consecutive_ones一脉相承。如果进一步要求“1 和 0 交替出现的最长模式”就涉及有限状态自动机了。我的经验是先用s.split(0)把字符串切开再求最长块的长度往往比动态规划更直观且更快。例如def longest_ones(s: str) - int: return max((len(part) for part in s.split(0)), default0)这个技巧在解析二进制报文、基因序列里的连续特征段甚至日志里连续成功标志时都有用。它的本质和全一数生成一样都是把一个规律性极强的结构投影到最简单的数学表达上。结尾一点真实体会把这套“算法111111”沉淀成独立模块之后我最大的感悟是很多看似复杂的算法真正的难点不在算法本身而在边界条件的定义和对底层数学结构的敏感度。一个简单的(1 n) - 1牵出的溢出控制、取模优化、字符串替代方案就足够写一整篇文章。我后来再遇到全一序列相关的需求已经形成条件反射先判断数据规模再选择位运算、公式还是字符串路径而不是无脑循环。最后再分享一个小技巧把类似x (x 1) 0的常用判断集中放在一个bit_utils.py文件里附上对应的测试用例以后新项目直接 import省下的调试时间远比当初写它的时间多。
