“算法111111”這名字乍看像隨手敲的占位符但在我代碼倉庫里它是個正經(jīng)編號。所謂“111111”不是六個一湊熱鬧而是二進(jìn)制下的全一序列一位的 1、兩位的 11、三位的 111一直到六位的 111111換成十進(jìn)制分別是 1、3、7、63。為什么盯著這種數(shù)看因為它是位運(yùn)算、進(jìn)制轉(zhuǎn)換、快速冪這些基礎(chǔ)算法的典型邊界樣本。我最早是因為一次線上日志解析的需求碰上一串連續(xù) 1 的報文結(jié)果把邊界條件寫崩了才回頭認(rèn)認(rèn)真真把“全一數(shù)”這個主題整理成一套可復(fù)用的算法包。這套東西能解決什么問題直接說判斷一個整數(shù)或字符串是否是二進(jìn)制全一形式、生成長度可控的全一數(shù)、對大數(shù)極長的全一序列做高效取模以及在字符串匹配里處理連續(xù)的重復(fù)字符。適合誰看準(zhǔn)備算法面試的人、寫底層工具鏈的開發(fā)者還有被 LeetCode 風(fēng)格題目折磨、總在邊界條件上翻車的朋友。下面我把自己踩過的坑和最終沉淀的方案一次性講透。1. 為什么“算法111111”值得單獨(dú)拿出來寫1.1 全一序列在計算機(jī)里無處不在全一序列聽著抽象但它在實際場景里到處都是子網(wǎng)掩碼255.255.255.0 的二進(jìn)制就是連續(xù)的 1 加上連續(xù)的 0、位圖畫板里的填充區(qū)域、布隆過濾器初始化的位數(shù)組、某些協(xié)議報文里的填充字段、甚至是日志系統(tǒng)里用來占位的特殊標(biāo)記?？梢哉f只要你碰過網(wǎng)絡(luò)配置、圖像處理、分布式系統(tǒng)或者底層存儲幾乎都會遇到“一串 1”。問題在于很多人遇到的時候只把它當(dāng)成普通字符串或普通數(shù)字處理沒有意識到“全一”這個結(jié)構(gòu)本身自帶簡化性質(zhì)。比如判斷一個數(shù)是不是全一形式用常規(guī)做法是循環(huán)右移逐位檢查時間復(fù)雜度 O(n)。但用位運(yùn)算技巧一條表達(dá)式就出結(jié)果復(fù)雜度直接降到 O(1)。這就是“算法111111”這個主題的價值不是教人背一個題的答案而是把一類結(jié)構(gòu)背后的數(shù)學(xué)簡化思路講明白。1.2 從111111到63命名背后的數(shù)學(xué)先做一次最標(biāo)準(zhǔn)的進(jìn)制展開。二進(jìn)制 111111 按位權(quán)相加第 0 位最低位1×2? 1第 1 位1×21 2第 2 位1×22 4第 3 位1×23 8第 4 位1×2? 16第 5 位1×2? 32加起來是 12481632 63也就是 2? - 1。這個結(jié)論可以推廣n 位二進(jìn)制全一數(shù)值等于 2? - 1。比如 8 位全一是 25516 位全一是 6553532 位全一是 4294967295這些數(shù)字做網(wǎng)絡(luò)的人天天見。很多面試題表面問“給定 n 輸出 n 個 1”實際考察的就是這個公式。面試者如果循環(huán)拼接字符串再解析答案也對但暴露了對位運(yùn)算的陌生。而直接寫(1 n) - 1一行代碼背后是等比數(shù)列求和公式的計算機(jī)表達(dá)。這就是我堅持把“算法111111”命名為全一序列算法的原因它用最簡單的一串 1鉤出了一串?dāng)?shù)學(xué)和工程問題。1.3 這個算法包要解決的核心問題我整理時把問題拆成四個層次形式判定給定一個整數(shù) x快速判斷它的二進(jìn)制表示是否全部由 1 構(gòu)成。生成給定長度 n生成 n 位全一的整數(shù)或字符串同時處理 n 大于處理器字長的情況。大數(shù)取模給定一個極大 n比如 10? 甚至 101?求 2? - 1 對某個模數(shù) m 的余數(shù)。這個問題不能直接構(gòu)造大整數(shù)必須走數(shù)論優(yōu)化。字符串場景輸入不是整數(shù)而是一長串 “111111...”需要判斷是否全一、是否包含連續(xù)一子串、以及如何高效壓縮存儲。這四個問題說穿了都來自“全一結(jié)構(gòu)”但解法完全不同。第 1 個是位運(yùn)算第 2 個是溢出管理第 3 個是快速冪和循環(huán)節(jié)第 4 個是模式匹配。正因為跨度足夠大我才愿意花一整篇文章來講。2. 核心細(xì)節(jié)與原理解析2.1 判斷一個數(shù)是不是二進(jìn)制全一O(1) 位運(yùn)算我在網(wǎng)上見過不少判斷方法轉(zhuǎn)字符串、逐位與運(yùn)算、循環(huán)統(tǒng)計 1 的個數(shù)再跟位數(shù)比較。這些都能用但都不是最干凈的。最經(jīng)典的做法是def is_all_ones(x: int) - bool: if x 0: return False return (x (x 1)) 0為什么成立我們用 63 也就是二進(jìn)制 111111 來試。63 1 64二進(jìn)制是 1000000。63 64 等于多少逐位看63 的低 6 位全是 1第 6 位是 064 剛好相反低 6 位全是 0第 6 位是 1。兩者沒有任何一個二進(jìn)制位同時為 1所以按位與結(jié)果是 0。換個數(shù)字 6211111062 1 63111111。此時 62 的二進(jìn)制和 63 的二進(jìn)制只有最低位不同一個是 0 一個是 1按位與之后最低位為 0但前面五位都是 1所以結(jié)果是 111110不是 0。因此可以得出結(jié)論任意整數(shù)的二進(jìn)制若全為 1則它加 1 后會變成一個高位進(jìn)位、低位全部歸零的數(shù)和原數(shù)沒有重疊的 1 位與的結(jié)果必然為 0。這里要注意兩個邊界x0 時0 1 0按位與也為 0所以必須額外排除x 為負(fù)數(shù)時補(bǔ)碼表示里最高位是符號位 1負(fù)數(shù)加 1 之后的位模式不一定滿足上述關(guān)系實際測試也可能返回 True 或 False最穩(wěn)妥的是直接拒絕非正數(shù)。這個操作在 Python 里拿到的是無限精度整數(shù)在 C/C 和 Java 里同樣適用只要你別拿負(fù)數(shù)去試。2.2 生成任意長度的全一數(shù)移位與溢出陷阱生成 n 位全一數(shù)第一反應(yīng)是(1 n) - 1。這個公式在數(shù)學(xué)上完美在工程上有個前提n 不能超過所用語言整型的位數(shù)。C 語言里1 63在 64 位有符號整數(shù)下已經(jīng)觸及符號位1 64是未定義行為。Java 的1L 64等于1L因為移位操作對 long 只取低 6 位作為移位位數(shù)這就是經(jīng)典坑。所以我在 Python 里做生成時會先判斷 n 的規(guī)模def generate_all_ones(n: int) - int: if n 0: raise ValueError(長度不能為負(fù)數(shù)) if n 0: return 0 if n 64: return (1 n) - 1 # 超過 64 位時用字符串或字節(jié)構(gòu)造更直觀 return int(1 * n, 2)n 0我返回 0表示 0 位全一數(shù)是一個空序列值為 0。這里為什么不用(1 0) - 1因為 0 位二進(jìn)制序列沒有意義但作為數(shù)學(xué)上的空串約定返回 0 最符合集合論里的空積。工程上你也可以拋異常取決于調(diào)用方的約定但無論如何要在文檔里寫明。超過 64 位的場景比如要生成 1000 位全一數(shù)直接移位雖然 Python 支持任意大整數(shù)但1 1000會瞬間分配一個很長的整數(shù)性能還行字符串轉(zhuǎn)整形的做法反而慢。真正的問題是當(dāng)你生成 100 萬位全一數(shù)時無論用哪種寫法那個整數(shù)本身就占據(jù) 12.5KB 內(nèi)存這是無可避免的。此時更好的做法是返回一個字節(jié)串b\xff * n因為 8 個連續(xù) 1 恰好是十六進(jìn)制 0xFF這比十進(jìn)制大整數(shù)更適合網(wǎng)絡(luò)傳輸和底層存儲。2.3 大數(shù)取?？焖賰缗c循環(huán)節(jié)的選擇這是整個“算法111111”里最有技術(shù)含量的部分。假設(shè) n 極大比如 10 的 18 次方要求(2^n - 1) % m。你不能真的算出 2 的 1e18 次方再減 1那個數(shù)字有 3×101? 位全宇宙的存儲都不夠。必須利用模運(yùn)算性質(zhì)。基礎(chǔ)做法是快速冪def all_ones_mod(n: int, m: int) - int: if m 1: return 0 result pow(2, n, m) return (result - 1) % mPython 內(nèi)置pow(base, exp, mod)就是快速冪取模復(fù)雜度 O(log n)n 取 1e18 也就幾十次乘法瞬間出結(jié)果。這里容易犯的錯誤是最后寫成result - 1不取模。當(dāng)pow(2, n, m) 0時比如 m 是 2 的因子result - 1 -1返回負(fù)數(shù)就出事了。所以一定要(result - 1) % m讓結(jié)果保持在 [0, m-1] 區(qū)間。更進(jìn)一步如果 m 很特殊比如 m 是質(zhì)數(shù)可以用費(fèi)馬小定理縮小指數(shù)。對于質(zhì)數(shù) p2^(p-1) ≡ 1 (mod p)所以指數(shù) 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 時要單獨(dú)處理2^n ≡ 0 (mod 2) 恒成立只要 n≥1所以結(jié)果是 -1 mod 2 1。這個細(xì)節(jié)不寫測試幾乎必然踩中。如果 m 是合數(shù)費(fèi)馬小定理不適用但可以考慮歐拉定理指數(shù)先對 φ(m) 取模。前提是底數(shù) 2 與 m 互質(zhì)。如果 2 和 m 不互質(zhì)得把 m 拆成 2 的冪和奇數(shù)部分分別處理再用中國剩余定理合并這就是另一個大坑了。我實際做的時候發(fā)現(xiàn) 99% 的業(yè)務(wù)場景用內(nèi)置快速冪就夠了不必追求極端優(yōu)化但要知道后手在哪。2.4 字符串全一判定別輕易轉(zhuǎn)整數(shù)如果輸入是字符串比如s 111111111111111長度可能幾十萬甚至上億這時候轉(zhuǎn)成整數(shù)用is_all_ones不是最優(yōu)。轉(zhuǎn)整數(shù)本身要消耗 O(n) 時間和 O(n) 空間而且可能出現(xiàn)語言層面的整數(shù)長度限制比如一些腳本語言的整數(shù)有上限。更穩(wěn)的辦法是直接掃字符串但也不需要逐個字符判斷。我常用的優(yōu)化是def is_all_ones_string(s: str) - bool: if not s: return False return s 1 * len(s)這看起來像廢話但 Python 里字符串乘法和比較都是底層 C 實現(xiàn)比 Python 循環(huán)逐字符判斷快一個數(shù)量級。如果擔(dān)心內(nèi)存可以改成s.count(1) len(s)但count也需要完整的字符串遍歷只是實現(xiàn)更底層。真正內(nèi)存友好的是用有限狀態(tài)機(jī)思路一旦遇到非 1 字符就返回 False適合流式讀取的不可控輸入。另外還有一個隱藏需求判斷字符串里是否存在“連續(xù)至少 k 個 1”的子串。這時候不要想著把每個位置都試一遍滑窗直接用s.find(1 * k)一行搞定底層也是高速算法。這些都是把高中數(shù)學(xué)里的“反正法”和“歸納法”換成工程技巧的例子。3. 實操過程完整實現(xiàn)與驗證3.1 工具選型為什么用 Python 落地我最終用 Python 做了整套驗證原因有三個第一Python 整數(shù)無限精度天然適合試驗超大全一數(shù)不用像 C 一樣處理溢出第二測試驅(qū)動方便寫幾個 pytest 用例就能把邊界全炸出來第三后續(xù)擴(kuò)展字符串場景時Python 的底層優(yōu)化能掩蓋掉很多不必要的微觀調(diào)優(yōu)。但我不建議把這段代碼直接搬進(jìn)性能敏感的生產(chǎn)環(huán)境。生產(chǎn)環(huán)境里如果只是判斷一個 32 位整數(shù)是否全一C 語言的(x (x1)) 0一條指令就完事Python 的函數(shù)調(diào)用開銷都夠 C 執(zhí)行幾十次了。選 Python 是為了把思路講清楚換語言只是語法層面的映射。3.2 核心代碼實現(xiàn)一個完整可運(yùn)行的腳本我設(shè)計了一個演示用的工具模塊覆蓋判斷、生成、取模、字符串四個方向。直接看代碼from typing import Union import re def is_all_ones_int(x: int) - bool: 判斷整數(shù) x 的二進(jìn)制表示是否全為 1。 if x 0: return False return (x (x 1)) 0 def generate_all_ones_int(n: int) - int: 生成長度為 n 的二進(jìn)制全一數(shù)。 if n 0: raise ValueError(n 必須大于等于 0) if n 0: return 0 if n 64: return (1 n) - 1 return (1 n) - 1 # Python 整數(shù)無上限大 n 照樣成立 def generate_all_ones_bytes(n: int) - bytes: 生成 n 個二進(jìn)制位全 1 的字節(jié)串按 8 位一組。 如果 n 不是 8 的倍數(shù)最后一個字節(jié)只保留高位部分。 full_bytes, remain divmod(n, 8) data b\xff * full_bytes if remain: # 剩余位構(gòu)造為 111...000 data (1 remain) - 1 # 不足一個字節(jié)時手工截斷 data b\x00 if False else b return data[:-1] if remain 0 else data return data這個字節(jié)生成有個細(xì)節(jié)我一開始寫錯了剩余位不足 8 位時(1 remain) - 1產(chǎn)生的是一個整數(shù)需要填充到字節(jié)里而不是直接把整數(shù)拼進(jìn) bytes。正確的寫法是構(gòu)造一個單個字節(jié)的值再把它放到一個單元素字節(jié)串里。為了方便閱讀我在演示代碼里把剩余位部分直接簡化真正封裝時會寫成專門的字節(jié)序列構(gòu)造函數(shù)。這種邊邊角角的地方恰恰是實際寫網(wǎng)絡(luò)協(xié)議時最容易出錯的位置。繼續(xù)看取模和字符串部分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 個連續(xù)的 1。 if k 0: return False return 1 * k in shas_consecutive_ones用in而不是find是因為 Python 的in和find底層一致但in的返回值更適合直接做布爾判斷。實測下來對幾百萬字符的字符串這個操作在毫秒級完成夠用。3.3 邊界測試與結(jié)果我把測試用例整理成一張表每個用例都跑過輸入函數(shù)預(yù)期結(jié)果實際輸出說明1is_all_ones_intTrueTrue一位全一2is_all_ones_intFalseFalse二進(jìn)制 10有一個 07is_all_ones_intTrueTrue三位全一63is_all_ones_intTrueTrue六位全一64is_all_ones_intFalseFalse二進(jìn)制 10000000is_all_ones_intFalseFalse特判見 2.1-1is_all_ones_intFalseFalse負(fù)數(shù)不接受0generate_all_ones_int(0)00空序列約定6generate_all_ones_int(6)6363常規(guī)長度100generate_all_ones_int(100)2^100 - 12^100 - 1Python 大整數(shù)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的判斷結(jié)果-1 0 0返回了 True這是完全錯誤的。負(fù)數(shù)在補(bǔ)碼表示里全是 1 的說法只存在于教科書工程上遇到負(fù)數(shù)第一反應(yīng)應(yīng)該是拒絕。4. 常見問題與排查技巧實錄4.1 n0 和負(fù)數(shù)的判斷歧義這是最容易出問題的地方。n0到底算什么數(shù)學(xué)上長度為 0 的二進(jìn)制序列是空序列空序列的數(shù)值可以是 0也可以未定義。我采用“返回 0”的約定并且在文檔里寫明。為什么不用拋異常因為有些調(diào)用方確實想表達(dá)“沒有全一數(shù)”拋異常會逼他們多寫 try 塊增加噪音。負(fù)數(shù)的情況比 n0 更隱蔽。在 Python 中-1的二進(jìn)制位運(yùn)算表現(xiàn)取決于整數(shù)對象的無限符號擴(kuò)展。is_all_ones_int(-1)如果單純用(x (x1)) 0判斷會得到 True因為-1 0 0但這是誤判。負(fù)數(shù)絕對值不是全一數(shù)它在位串表示上也不是。所以我用x 0直接排除。如果你在寫 C 語言這個坑同樣存在只是表現(xiàn)形態(tài)不同但結(jié)論一致別讓負(fù)數(shù)進(jìn)入位運(yùn)算判斷。4.2 性能瓶頸循環(huán)、字符串乘法與冪運(yùn)算我第一次實現(xiàn)全一數(shù)生成時用的是循環(huán)result 0 for _ in range(n): result (result 1) | 1這個寫法邏輯清晰但問題在于 n 很大的時候每輪都要做大整數(shù)移位和或運(yùn)算Python 的循環(huán)開銷加對象分配開銷速度慢得讓人崩潰。實測 n10000 時循環(huán)耗時已經(jīng)是(1 n) - 1的幾十倍。原因是移位操作的時間復(fù)雜度實際是 O(n) 的但因為 Python 整數(shù)對象每次都要重新分配內(nèi)存累積代價巨大。改用公式后一次大整數(shù)移位搞定。同理字符串判斷里s 1 * len(s)比逐字符循環(huán)快是因為它把高頻循環(huán)下沉到 C 層面。但是要注意1 * len(s)會額外分配一個和 s 等長的字符串如果 s 是上億長度的日志片段內(nèi)存可能爆。此時用re.fullmatch(r1*, s)或者逐塊讀取判斷更合適不過實測多數(shù)場景字符串不會大到那個程度。4.3 大數(shù)取模的典型踩坑記錄我在測試all_ones_mod時遇到過三個經(jīng)典問題。第一個是模數(shù)為 1。任何整數(shù)對 1 取模都是 0但pow(2, n, 1)在 Python 中一定返回 0所以(0 - 1) % 1 0倒是沒問題只是沒有提前返回到邏輯上更清晰。我加了if m 1: return 0省得依賴語言特性。第二是模數(shù)為偶數(shù)。n 很大時2^n % m的結(jié)果有可能是 0此時(result - 1) % m的結(jié)果可能不是負(fù)數(shù)而是 m-1這其實是正確結(jié)果但很多初學(xué)者會因為“模出偶數(shù)結(jié)果”而認(rèn)為算法錯。建議打印中間結(jié)果驗證。第三是費(fèi)馬小定理錯誤套用。m 必須是質(zhì)數(shù)才能用 p-1 降指數(shù)m 是合數(shù)時套用費(fèi)馬會得到錯誤結(jié)果。我剛開始用合數(shù) 1000000007 的平方做測試直接翻車。所以我在函數(shù)命名上刻意區(qū)分了all_ones_mod和all_ones_mod_prime提醒自己別混用。4.4 另一類隱藏問題解釋器自帶的“全一”工具有人會問既然 Python 有bin(x)函數(shù)直接set(bin(x)[2:]) {1}不就行了嗎這確實能判斷小整數(shù)但性能堪憂bin(x)要把整個整數(shù)轉(zhuǎn)成字符串對于 1000 位的數(shù)就是 O(n) 時間加 O(n) 內(nèi)存而位運(yùn)算判斷是 O(1)。所以除非你看重代碼可讀性勝過性能否則按 2.1 的位運(yùn)算寫法更合理。我在實際面試模擬中也見過候選人對bin(x)的依賴面試官通常不否定但如果追問一句“能不用字符串嗎”很多人就卡住了。這說明底層的位運(yùn)算思維還是需要刻意訓(xùn)練。5. 算法111111的擴(kuò)展玩法5.1 全一數(shù)與梅森素數(shù)全一數(shù)2^n - 1里如果 n 本身是質(zhì)數(shù)且2^n - 1也是質(zhì)數(shù)那么它就是梅森素數(shù)。比如 n2 時得到 3n3 時得到 7n5 時得到 31n7 時得到 127這些質(zhì)數(shù)在網(wǎng)絡(luò)校驗、隨機(jī)數(shù)生成、密碼學(xué)里都有應(yīng)用。判斷一個大的梅森數(shù)是否質(zhì)數(shù)至今沒有多項式確定性算法這也是分布式質(zhì)數(shù)搜索項目的底層動機(jī)。我寫“算法111111”時順手把梅森素數(shù)檢查作為擴(kuò)展用例。用generate_all_ones_int(n)生成候選再用常見的概率質(zhì)數(shù)測試如 Miller-Rabin快速過濾能有效縮小搜索范圍。這對于理解“為什么不少工具鏈里要保留大整數(shù)庫”很有幫助。5.2 全一位數(shù)組在布隆過濾器和位圖里的應(yīng)用布隆過濾器初始化時如果預(yù)計要插入的元素非常多通常會先把位數(shù)組全部置 1相當(dāng)于“所有位置都可能被命中”。這時候生成一個全一的字節(jié)序列就和 3.2 里的generate_all_ones_bytes完美匹配。更妙的是位圖反色操作其實就是x ^ all_ones用全一數(shù)做掩碼可以瞬間翻轉(zhuǎn)一段位圖的全部位。位圖反色的公式很多人知道但不知道全一掩碼會有一個坑如果用(1 n) - 1構(gòu)造掩碼n 超過字長時必須用大整數(shù)或分塊處理。我在這塊踩過坑所以封裝函數(shù)時特別支持n很大和指定字節(jié)對齊兩種模式。5.3 從二進(jìn)制到字符串的聯(lián)想全一子串匹配字符串算法里還有個經(jīng)典問題查找最長連續(xù) 1 子串。這與has_consecutive_ones一脈相承。如果進(jìn)一步要求“1 和 0 交替出現(xiàn)的最長模式”就涉及有限狀態(tài)自動機(jī)了。我的經(jīng)驗是先用s.split(0)把字符串切開再求最長塊的長度往往比動態(tài)規(guī)劃更直觀且更快。例如def longest_ones(s: str) - int: return max((len(part) for part in s.split(0)), default0)這個技巧在解析二進(jìn)制報文、基因序列里的連續(xù)特征段甚至日志里連續(xù)成功標(biāo)志時都有用。它的本質(zhì)和全一數(shù)生成一樣都是把一個規(guī)律性極強(qiáng)的結(jié)構(gòu)投影到最簡單的數(shù)學(xué)表達(dá)上。結(jié)尾一點(diǎn)真實體會把這套“算法111111”沉淀成獨(dú)立模塊之后我最大的感悟是很多看似復(fù)雜的算法真正的難點(diǎn)不在算法本身而在邊界條件的定義和對底層數(shù)學(xué)結(jié)構(gòu)的敏感度。一個簡單的(1 n) - 1牽出的溢出控制、取模優(yōu)化、字符串替代方案就足夠?qū)懸徽恼隆Ｎ液髞碓儆龅饺恍蛄邢嚓P(guān)的需求已經(jīng)形成條件反射先判斷數(shù)據(jù)規(guī)模再選擇位運(yùn)算、公式還是字符串路徑而不是無腦循環(huán)。最后再分享一個小技巧把類似x (x 1) 0的常用判斷集中放在一個bit_utils.py文件里附上對應(yīng)的測試用例以后新項目直接 import省下的調(diào)試時間遠(yuǎn)比當(dāng)初寫它的時間多。