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