刷LeetCode刷到1680题的时候我第一反应是这不就是把1到n的二进制串拼起来转成十进制再取个模吗字符串拼接、进制转换、取模三步走完完事。直到我在本地把暴力版和位运算版分别跑了一遍才意识到这道题真正值钱的不是怎么AC而是能不能从“字符串视角”切换到“数值视角”。这篇文章就把我从暴力版到位运算版的完整思考过程写下来包括讨论区里不太会有人详细讲的数据范围推算、取模时机和溢出问题。题目本身不难但里面每个细节都能牵出一串二进制处理的通用技巧适合刚刷位运算的初学者也适合想把这套“拼接即左移”思路迁移到其他题型的同学。1. 从题目直译到本质转化拼接动作背后的数学含义1.1 三个示例建立直觉题目直译给你一个整数n把1到n的每个十进制整数写成二进制去掉前缀0b按顺序首尾相连得到一个很长的二进制串最后把这个串当二进制数转回十进制并模1e97。手推几个小例子n1只有“1”结果是1。n21是“1”2是“10”连起来是“110”值是6。n3再拼上3的“11”得到“11011”值是27。n4加上4的“100”得到“11011100”值是220。如果你只看字符串容易觉得这事就是拼接。但你再看一眼递进关系110变成11011发生了什么其实等于把110左移2位——6左移2位是24再加上3等于27。所以“往字符串尾部追加一个二进制数字”这个动作用数值语言来说就是两件事整串左移新数字的位数然后在这个腾出来的低位空间里放上这个数字本身。这里可以放一个生活类比在十进制里把27后面追加两位数字99等于27乘100再加99。二进制不是乘以100而是乘以2^k其中k是追加数字的二进制位数。这一个翻译是整个解法的全部核心。1.2 为什么最终要取模结果长度的指数感顺手说一下范围。n4时最终二进制串是8位n100000呢每个数平均约17位总长度约150万位。150万位的二进制数转成十进制大约有45万位Python大整数能顶住但C没有内置大整数直接爆。这也是为什么题目规定要对1e97取模。取模不会让“拼接加转值”的字符串方案变快它只是让最终结果能用一个普通整数存下。但如果你用数值递推法取模还能顺便把中间数的规模压住避免大整数运算拖慢程序。这个区别后面实测会看得非常明显。2. 字符串暴力版为什么能过却不能这么写2.1 最直接的实现方式暴力版代码很短Python甚至三行class Solution: def concatenatedBinary(self, n: int) - int: s .join(bin(i)[2:] for i in range(1, n 1)) return int(s, 2) % (10**9 7)这段在n1e5时能不能过LeetCode能。C用string累积应该也能过Java如果用StringBuilder也能过。如果你只追求AC暴力确实是一条路很多人的题解也就是这么写的。2.2 复杂度真相与“能过”背后的隐患但“过了”不代表“合理”。我们来算一笔账。最终二进制串的总位数L(n)等于sum_{i1}^{n}(floor(log2 i) 1)。n1e5时大概是100000乘17减去(2^17 - 2)约等于1700000减131070结果是1568930。大约156万位。字符串拼接本身O(L)转大整数int(s, 2)在Python内部是O(L^2)量级的逐位累加150万位跑下来其实也要一两百毫秒。看着不多但这种实现完全没法承受数据范围扩大。n提到1e6总位数变成约2000万Python的int(s, 2)会卡到十几秒甚至更久n到1e9光二进制串就是280亿位内存直接爆暴力方案连边都摸不到。还有一层隐患是不同语言的差距。你在C里写string循环追加vector摊销后还在O(L)但如果你在Java里写String s ; s curBinary;那是O(L^2)的字符串反复拷贝n1e5就能给你拖到几秒。同样是暴力语言特性会让难度天差地别。刷题时看到过不少人在Java版块抱怨这道题超时十有八九就是栽在String重复拼接上。2.3 我的实测对比我本地跑过一次三种版本对比Python字符串版约300ms上下主要是int(s, 2)这一下吃时间。C string版约20ms上下。Java StringBuilder版约30ms上下Java裸String拼接版则直接飙到3s以上。而位运算递推版也就是后面给出的代码Python大约20msC大约2msJava大约3ms。也就是说即便语言自己“扛得住”字符串方案也天然比数值方案慢一个数量级以上。更关键的是字符串方案没办法回答一个自然的追问如果n是1e9呢位运算递推虽然也回答不了1e9O(n)超时但它给出的递推结构可以直接升级成按长度分组的矩阵快速幂解法这就是后面第五节的内容。字符串方案则没有任何升级余地。3. 位运算递推把“拼接”变成一行公式三种思路先摆在一张表里心里有个全貌再往下看思路核心操作时间复杂度空间复杂度主要代价字符串拼接join int(s, 2)O(n log n)转大整数更贵O(L)表达直观但无法处理更大n部分语言易超时位运算递推ans (ans len) iO(n)O(1)需要维护len并处理取模时机分组矩阵快速幂每组一次矩阵快速幂O(log^2 n)O(1)实现复杂n极大时才划算3.1 递推公式推导与手工验算设f(i)表示“1到i的二进制串拼接后对应的十进制数值”len(i)表示i的二进制位数。从i-1到i我们做的事情是把f(i-1)的二进制串左移len(i)位然后加上i。写成公式f(i) (f(i-1) len(i)) i f(i-1) * 2^len(i) i为什么左移len(i)位因为二进制串尾部要腾出len(i)个空位来放i的二进制。左移一位等于乘2左移len(i)位等于乘2^len(i)。拿n4代入走一遍。初始ans0bit_len0i1时100成立bit_len变1ans(01)11i2时210成立bit_len变2ans(12)26i3时322不为0bit_len保持2ans(62)327i4时430成立bit_len变3ans(273)4220结果220和手推的“11011100”完全一致。这段走查能发现递推式的每一步都对应着“把已有串左移新数的位数再填上新数”。有了递推式代码就只剩两件事维护f以及计算len(i)。维护f需要取模因为模运算满足(a乘b加c)模mod等于((a模mod)乘b加c)模mod所以每轮算完就取模不会影响最终结果还能把f的值压到1e9以内保证后续左移不撑爆整数类型。3.2 如何优雅维护二进制位数len(i)这里有一个很容易被忽略的观察i的二进制位数不是每加1都变的它只在跨越2的幂时增加1。1是1位2到3是2位4到7是3位8到15是4位以此类推。所以维护一个变量bit_len每次循环里如果i正好是2的幂就把bit_len加1。判断2的幂的经典位运算是i (i - 1) 0。于是ans 0 bit_len 0 for i in range(1, n 1): if i (i - 1) 0: bit_len 1 ans ((ans bit_len) i) % MOD这段代码有个很顺的巧合i1时100成立bit_len从0变成1恰好满足1是1位数。所以不需要特判循环内一行判断就全包了。另一种更直白的写法是每次调i.bit_length()但我觉得维护一个变量更贴合“位运算”这道题的气质也避免对语言内建函数的依赖。两种写法在n1e5时的性能差距可以忽略但如果n再大一个量级位判断那一点常数优势会略微体现。3.3 三种语言实现对比Pythonclass Solution: def concatenatedBinary(self, n: int) - int: MOD 1_000_000_007 ans 0 bit_len 0 for i in range(1, n 1): if i (i - 1) 0: bit_len 1 ans ((ans bit_len) i) % MOD return ansCclass Solution { public: int concatenatedBinary(int n) { const int MOD 1e9 7; long long ans 0; int bit_len 0; for (int i 1; i n; i) { if ((i (i - 1)) 0) bit_len; ans ((ans bit_len) i) % MOD; } return (int)ans; } };Javaclass Solution { public int concatenatedBinary(int n) { final int MOD 1_000_000_007; long ans 0; int bit_len 0; for (int i 1; i n; i) { if ((i (i - 1)) 0) bit_len; ans ((ans bit_len) i) % MOD; } return (int) ans; } }三份代码逻辑完全一样唯一要注意的是C和Java的中间变量必须用64位整数。至于为什么下一节专门讲。4. 取模、溢出、边界三个最容易写错的细节4.1 先移位还是先取模顺序决定会不会溢出ans ((ans bit_len) i) % MOD这句看起来平淡其实每一步都踩在边界上。ans上一轮已经取过模最大值是MOD-1约1e9bit_len在n1e5时最大是17所以ans bit_len最大约1e9乘1.3e5约1.3e14。这个数在long long范围内绰绰有余。再加i也在1e14量级取模后回到1e9整体路径安全。但如果你把顺序改成先加后移位比如ans ((ans i) bit_len) % MOD意义上就完全错了你先把i加进去再整体左移结果等于i也被左移了而正确的语义是i只占低bit_len位。这种顺序错误在代码审查里很难一眼看出来最好用自己的暴力版打表验证。还有一种是ans (ans * (1 bit_len) i) % MOD。在本题范围内1 bit_len最大是117没问题。但如果n加大到1e9bit_len会到30130也才约10.7亿依然在int里到n更大时1 bit_len会溢出int必须写成1LL bit_len这是一个非常经典的隐式类型转换坑。4.2 C/Java为什么必须用long long / long如果ans用int在第一轮循环还好后面ans接近1e9左移17位直接溢出结果变成垃圾值提交后大概率WA。这类溢出错误在LeetCode上非常常见不报错、不警告只会给你一个看似完全没有逻辑的答案。我见过不少人把代码改成long之后一头雾水不知道自己刚才错在哪。记住这条铁律只要代码里出现左移后还打算加数、取模中间变量一律用64位整数哪怕你觉得“数据范围最大才1e5”。顺便给个具体数字感受一下当ans取模后是10亿左移17位相当于乘131072结果约1.31e14。而int最大约21.47亿这个数字超出int范围约6万倍。C的整数溢出是未定义行为常见表现是结果变成0或一个看起来随机的负数。Java的int溢出则是回绕变成负的截断值同样是灾难。4.3 边界条件自查清单我每次写完位运算递推至少会检查这几个位置n1ans1bit_len在i1时从0变1结果1正确。n21的“1”和2的“10”拼成“110”6正确。n73位数的起点验证bit_len在i4时从2变3是否生效。n84位数的起点i8时bit_len从3变4。n100000和暴力版比对最终答案。这里最容易被忽略的是2的幂本身。i32时二进制是100000占了6位而31是11111只有5位。从31跨到32bit_len必须加1。如果你用别的公式算len比如log2(i)1向下取整也要保证在边界上的计算不出误差。浮点log2在这种边界上是会出问题的所以尽量别拿库函数算位数。我写了这样一个自测脚本每次改动实现后跑一遍能挡住绝大多数低级错误def brute(n): s .join(bin(i)[2:] for i in range(1, n 1)) return int(s, 2) % (10**9 7) def fast(n): MOD 10**9 7 ans 0 bit_len 0 for i in range(1, n 1): if i (i - 1) 0: bit_len 1 ans ((ans bit_len) i) % MOD return ans for n in range(1, 500): if brute(n) ! fast(n): print(mismatch at, n) break else: print(all ok)5. 进阶推演当n大到1e9O(n)解法如何升级5.1 分组的直觉位运算递推是O(n)的n1e5完全够用。但如果这是一道变体题n给到1e9O(n)必然超时。怎么优化答案是回到递推公式本身按二进制位数分组。每个数i的bit_len只可能是1、2、3、...、30n1e9时最多到30。所有bit_lenk的数字构成一个区间[2^(k-1), 2^k - 1]。在一个区间内拼接操作的形式是固定的新结果 旧结果乘2^k 当前数字这跟普通递推唯一的区别是2^k在组内是常量。于是组内连续拼接m个数字就等价于对“旧结果”反复应用同一个线性变换。线性变换可以用矩阵表示。构造向量(ans, i, 1)一次拼接的转移是ans ans乘2^k ii i 11 1所以转移矩阵是[2^k, 1, 0] [0, 1, 1] [0, 0, 1]组内数字个数cnt等于R减L加1对矩阵做cnt次方再乘上初始向量就能一口气算出这一组拼接完的结果。矩阵快速幂的复杂度是O(log cnt)不是O(cnt)。总共有O(log n)个组所以整体复杂度降到O(log n乘log n)n1e9也就几十次3x3矩阵乘法秒出结果。5.2 矩阵快速幂的参考实现这套实现我大概写过两三次每次都要重新推导矩阵的每一项所以干脆放一个Python版在这里需要时直接抄框架class Solution: def concatenatedBinaryFast(self, n: int) - int: MOD 10**9 7 def mul(a, b): return [[sum(a[i][t] * b[t][j] for t in range(3)) % MOD for j in range(3)] for i in range(3)] def mat_pow(m, e): res [[1 if i j else 0 for j in range(3)] for i in range(3)] while e: if e 1: res mul(res, m) m mul(m, m) e 1 return res ans 0 k 1 while (1 (k - 1)) n: L 1 (k - 1) R min((1 k) - 1, n) if L R: break cnt R - L 1 M [[(1 k) % MOD, 1, 0], [0, 1, 1], [0, 0, 1]] Mp mat_pow(M, cnt) ans (Mp[0][0] * ans Mp[0][1] * L Mp[0][2]) % MOD k 1 return ans注意一点矩阵第二、三行负责i的自增但我在组与组之间只提取第一行用来更新ans下一组的起点L会重新赋值所以不需要关心变换后向量第二项的数值。实际上它把i从1连续推到n1逻辑上也自洽只是代码没用到罢了。5.3 不写矩阵的话组内拼接也能用等比级数理解从L拼到R等价于res res乘(2^k)^m L乘(2^k)^(m-1) (L1)乘(2^k)^(m-2) ... R乘(2^k)^0m是组内数字个数。右边那个求和本质上是一个等比数列每一项额外乘了一个一次多项式(Lt)可以拆成两个几何和的线性组合在O(log m)内求出。矩阵法就是这个式子的线性代数封装两者本质相同。理解了这一点你在纸上手推任意范围内的拼接结果都会更快面试时如果被追问“n很大怎么办”也能多一条可讲的思路。6. 拼接即左移这个思路能迁移到哪些场景6.1 状态压缩与哈希滚动“往二进制尾部追加一段信息左移后或上信息”这句话在不同的题里换着面孔出现。最典型的就是状态压缩DP。你用一个整数表示一排格子的开关状态要在这排格子后面再接一个新格子的状态就是state (state 1) | bit。这和本题的递推只差一个取模本质上都是“尾部拼接”。另一个几乎同构的场景是字符串滚动哈希。Rabin-Karp里每读一个字符hash更新为hash hash * base val。看着是乘base不是移位但二进制只是base2的特例把“进制”这个概念抽象出来这跟本题的ans * 2^len i是同一件事。理解一个等于理解一整类。还有一个反向用法我经常在解析二进制协议时用给你一个字节数组要把它们解释成一个长整数从高字节往低字节累积就是value (value 8) | byte中间遇到某个字段要跳过或改位就提前设计一个mask。这跟本题的“尾部追加”思想完全一致只是把len从1换成了8。6.2 相关二进制题型的迁移顺着这个思路我建议刷题时把这几道题放在一起对比LeetCode 1016判断一个大二进制串里的子串是否覆盖了1到n的二进制表示。它正好是本题的逆向视角从“拼接”变成“反查”同样要用到长度分组的想法。LeetCode 191统计二进制中1的个数Brian Kernighan算法里有一行n n - 1和本题判断2的幂是同一个位运算家族。LeetCode 231判断是否为2的幂直接用n 0 (n (n - 1)) 0就是本题维护bit_len的那个判断。这个迁移不是刷题数量上的堆砌而是它们共享同一套“位串即数、拼接即移位”的世界观。把这套东西内化之后看到“二进制”三个字你的第一反应就不会是“先拼字符串再转十进制”而是“能不能找到一条按位移动的递推路径”。写到这里我反而觉得1680这道题最有趣的地方不是AC本身而是它把“字符串视角”和“数值视角”之间的那道墙轻轻捅破了。之后你再遇到任何进制拼接、二进制压缩、状态编码的题目都会下意识多点一层数学推导而不是直接往字符串里塞。这个转变比一道题的AC记录值钱得多。