最近在整理位运算的练习单又翻到了 LeetCode 1680 这道题。单看名字“连接连续二进制数字”像一道字符串处理题其实真正想考的是你对二进制表示、左移、取模这些东西的理解程度。我第一次做的时候脑子里第一反应也是“把二进制字符串拼起来再转十进制”直到自己动手跑了一遍才发现这个思路只是能过小数据放到题目要求的 n 上限就有点难受了。这篇文章会把这道题从题目意思、核心公式、三份代码到踩坑记录完整拆一遍。不管你是准备算法面试还是平时要写底层、网络协议、数据封包相关的代码都值得花十分钟把它看透。1. 题目到底在问什么输入输出与示例拆解1.1 原题描述与数据范围LeetCode 1680 的原题描述很简短给你一个整数 n请你返回 1 到 n 的二进制表示按顺序连接而成的二进制字符串所表示的十进制整数对10^9 7取模的结果。几个关键信息需要先划出来连接范围是从 1 开始不是从 0 开始所以第一位永远是 1这会给后面验证一些小细节带来方便。连接顺序必须保持 1、2、3、…、n不能调换不能省略。最终要把一整串二进制数当成一个二进制整数换算成十进制并且对1000000007取模。数据范围是1 n 10^5。这个范围不算大但也不算小到能让你随便构造一个超大字符串再转换。看一下官方示例会更直观。n二进制连接十进制11121106311011274110111100220n 等于 1 时只有二进制1结果是 1。n 等于 2 时把1和10拼起来得到110也就是十进制的 6。n 等于 3 时1 10 11 11011十进制是 27。n 等于 4 时继续拼上100得到110111100十进制是 220。n12 时最终字符串是1101110010111011110001001101010111100这个二进制数非常大对10^9 7取模后答案是505379714。等你自己写完代码可以用这个样例验证。1.2 二进制连接的手工推演要真正理解这道题我得先带你手算一次。比如要拼接两个二进制数110 和 11。110 是十进制 6。11 是十进制 3。把 110 和 11 拼在一起得到 11011也就是十进制 27。这个拼接过程从数值上看发生了什么其实和十进制拼接完全同理。十进制的数字 12 和 34 拼接成 1234本质是12 * 10^2 34因为 34 是两位数所以要给 12 腾出两位。二进制的 110 和 11 拼接因为 11 是两位所以要给 110 腾出两位也就是110 * 2^2 11等于11000 11即11011。这个“腾位置”的操作就是左移。二进制里往左移一位相当于乘以 2往左移两位相当于乘以2^2。所以“二进制拼接”本质上不是一个字符串操作而是一个数学操作。把这一点想通整道题的核心思路就清晰了。1.3 为什么先拼字符串再转大整数不是好方案有些朋友会想反正 n 只有 10^5我先把所有二进制串拼成一个长字符串然后用语言自带的大整数转换函数转成整数取模不就行了理论上能算但工程上不划算。先估算一下最终字符串的长度。到 n100000 时二进制位数的分布大致是1 只有 1 位2 到 3 是 2 位4 到 7 是 3 位……每到一个 2 的幂位数就加 1。把 1 到 100000 所有数的二进制位数加起来大概有 157 万字符。这个长度看起来不算离谱Python 的int(s, 2)也确实能转。但问题有两个一是字符串拼接如果写成循环s bin(i)[2:]在 Python 里是 O(L^2) 的时间会非常慢就算你用列表收集后再join157 万字符的字符串和对应的超大整数也要占不少内存。二是题目背后的考点是位运算用字符串等于绕过了核心思路面试时很难拿高分。如果你把 n 放大到 10^6字符串方案基本就跑不动了而位运算方案仍然能轻松处理。2. 核心思路用位运算滚动拼接2.1 二进制拼接的数学本质左移加低位上一节已经推出了关键公式。假设当前结果是一个整数ans下一个要拼接的数字是i而i的二进制长度是L。那么拼接后的新结果等于ans * 2^L i换成位运算的写法就是(ans L) | i或者写成(ans L) i因为ans左移L位后低L位全部是 0此时i一定会被放进这些空位不会和ans原有的位出现重叠。所以按位或和加法在这个场景下完全等价。举一个三步的例子帮你建立直觉当前 ans二进制当前 iL计算过程新 ans二进制011(0 1) 11122(1 2) 2110632(6 2) 3110112743(27 3) 4110111100从这张表能看到ans会越来越长但每一步都只处理“当前这个数需要占用几位”已经拼好的高位部分不会受到干扰。这就是滚动拼接。2.2 如何快速得到 i 的二进制位数整个算法里最关键的输入就是L。L等于i的二进制位数也就是数学上的floor(log2(i)) 1。最直观的写法是循环右移int L 0; for (int x i; x 0; x 1) L;这个写法永远不会错但每一轮都要做最多 17 次右移因为 n 最多 10^5位数最多 17。实际运行下来这点开销完全可以忽略。不过既然题目练的是位运算更地道的做法是用语言内置的“数前导零”接口C 里用32 - __builtin_clz(i)。Java 里用32 - Integer.numberOfLeadingZeros(i)。Python 里直接用i.bit_length()。语言写法说明C32 - __builtin_clz(i)只对正数 i 有效i 从 1 开始安全Java32 - Integer.numberOfLeadingZeros(i)语义与 clz 一致Pythoni.bit_length()最省事语义直白通用循环右移写法最稳适合做兜底这里特别提醒一下 C 的写法。__builtin_clz接收的参数是unsigned int传入普通int一般没问题但如果你写的代码要兼容 i 可能是 0 的情况clz的行为是未定义的。本题 i 从 1 开始所以不用踩这个坑但养成习惯还是要注意参数类型。2.3 每一步取模的时机题目要求结果对10^9 7取模。为什么不先算出完整整数再取模因为真正的结果有上百万位二进制位在 C 和 Java 里用long long根本装不下。就算你用 Python 的大整数硬扛最后转换和运算的开销也比滚动取模大得多。取模运算有一个非常好的性质加法和乘法对模运算都是“可分配”的也就是(a b) % MOD (a % MOD b % MOD) % MOD (a * b) % MOD ((a % MOD) * (b % MOD)) % MOD左移L位本质上是乘以2^L所以每一步都可以安全地取一次模ans ((ans L) i) % MOD这保证ans始终在[0, MOD)范围内。在 C 或 Java 里ans用一个long long就够了不会溢出。后面第 5 节我会专门算一笔账解释为什么这样写不会爆掉 64 位。3. 代码实现C / Python / Java 三语对照3.1 C 版本先看用__builtin_clz的版本class Solution { public: int concatenatedBinary(int n) { const long long MOD 1000000007LL; long long ans 0; for (int i 1; i n; i) { int len 32 - __builtin_clz(i); ans ((ans len) i) % MOD; } return (int)ans; } };如果担心__builtin_clz移植性可以用循环右移版代码更稳class Solution { public: int concatenatedBinary(int n) { const long long MOD 1000000007LL; long long ans 0; for (int i 1; i n; i) { int len 0; for (int x i; x 0; x 1) len; ans ((ans len) i) % MOD; } return (int)ans; } };C 里最容易出错的地方是类型。ans一定得是long long不能写成int。因为ans虽然每次都被取模但ans len这一步在执行完取模之前可能已经超过int范围。举个例子ans如果等于 10 亿左移 17 位结果大约是 1.3 万亿早就撑爆 32 位了。3.2 Python 版本Python 写起来最简洁因为大整数天然支持任意长度class Solution: def concatenatedBinary(self, n: int) - int: MOD 10**9 7 ans 0 for i in range(1, n 1): length i.bit_length() ans ((ans length) i) % MOD return ansbit_length()是 Python 整数自带的方法返回二进制表示去掉前导零后的位数。i1时返回 1i4时返回 3语义完全对应公式里的 L。不过要提醒一句Python 里的大整数位移并不是严格 O(1) 的操作。ans会随着循环不断变长实际位操作成本会逐渐增大。好在这一题 n 最大只有 10^5最终ans的有效位数也不到 160 万位跑下来依然是毫秒级别完全够用。3.3 Java 版本class Solution { private static final long MOD 1000000007L; public int concatenatedBinary(int n) { long ans 0; for (int i 1; i n; i) { int len 32 - Integer.numberOfLeadingZeros(i); ans ((ans len) i) % MOD; } return (int) ans; } }Java 的Integer.numberOfLeadingZeros和 C 的__builtin_clz语义几乎一模一样都是数出一个 32 位整数从最高位开始连续有多少个 0。i是正数所以返回 0 到 31 之间的值用 32 减一下就是位数。三份代码的核心逻辑完全一致区别只在计算len的方式。我个人的习惯是写 LeetCode 时用内置函数写生产代码或者需要跨编译器时用循环右移版本因为循环右移没有任何未定义行为也不用担心编译器差异。4. 复杂度分析与进一步优化4.1 标准复杂度从算法层看C 和 Java 的版本最多执行 n 次循环每次循环做一次左移、一次加法、一次取模都是常数时间。所以时间复杂度是 O(n)空间复杂度是 O(1)。Python 版本因为大整数位移的底层开销严格说是 O(n * M)其中 M 是ans的平均位数约等于 80 万位。但这个常数在实际运行时很小LeetCode 上也能轻松通过。如果你要跟别人讲复杂度可以先说标准 O(n)再补一句“Python 大整数底层不是固定位宽所以严格分析会比 C 多一个位数因子”。4.2 连续长度段优化减少 bit_length 的调用次数还有一个很实用的小优化二进制长度其实不是每个数都变化的它只在遇到 2 的幂时加 1。比如 1 的长度是 12 和 3 的长度是 24 到 7 的长度是 38 到 15 的长度是 4。所以可以维护一个len变量每当i等于2^len时len加 1。循环里不需要再调用clz或bit_lengthclass Solution { public: int concatenatedBinary(int n) { const long long MOD 1000000007LL; long long ans 0; int len 1; int nextPower 2; for (int i 1; i n; i) { if (i nextPower) { len; nextPower 1; } ans ((ans len) i) % MOD; } return (int)ans; } };这版代码在 i 等于 2、4、8、16 这些数时把len往上加其他位置保持不变。它和clz版结果完全一样但省去了每轮计算位数的开销逻辑也更贴近“二进制位数分段分布”的本质。如果你在面试里写出这个版本面试官会知道你确实理解了位数的变化规律。4.3 更进一步的数学优化思路如果有一天题目把 n 放大到 10^9O(n) 就不够了这时候可以把整个区间按照二进制位数分成若干段。每一段里的所有数位数相同段的长度是 2 的幂例如位数 1 的段11 个数位数 2 的段2 到 32 个数位数 3 的段4 到 74 个数位数 k 的段2^(k-1) 到 2^k - 12^(k-1) 个数每一段内部实际上是对一个连续整数序列做等长移位累加。利用等比数列求和公式可以整段计算出结果而不必逐个数去拼。这样可以把时间复杂度降到 O(log^2 n) 级别。不过这个写法要处理模意义下的除法、快速幂等细节对 n10^5 属于过度设计我这里就不展开完整实现了。你只要知道这个优化方向存在面试被问“n 更大怎么办”时能说出思路即可。4.4 实测表现字符串方案 vs 位运算方案我在本地跑过一个简单对比n100000 时方案大致表现列表收集所有二进制字符串再 join能跑但 L 有 157 万字符内存占用明显循环字符串拼接s bin(i)[2:]很慢字符串反复拷贝时间复杂度接近 O(L^2)逐项位运算滚动拼接很快C 版本几个毫秒Python 版本也在百毫秒量级这个对比不是想说明字符串方案“完全不能跑”而是想说在大数据范围下正确理解问题本质能让你少走很多弯路。位运算方案不管在时间、空间还是代码可读性上都是更优选择。5. 常见问题与排查实录5.1 为什么不能用简单的 ans i 来拼接这是新手最容易犯的错误。有人看到公式(ans L) i觉得麻烦想直接用ans i结果算出来的数对不上。原因很简单如果不把ans左移 L 位i就会直接覆盖在ans的低位上而不是接在ans后面。比如ans 110i 3如果直接相加得到110 11 1001也就是十进制 9而正确的拼接是11011十进制 27。差了 3 倍不止。在二进制世界里“拼接”永远意味着“给旧值腾出足够的空位”这个空位宽度由新值的位数决定。左移就是腾空位的手段。5.2 bit_length 算错导致答案整体偏小如果你实现的答案在小 n 时就不对先检查len的计算。我自己踩过的一个坑是 C 里把32 - __builtin_clz(i)写成了31 - __builtin_clz(i)。对于 i1clz是 3131 - 31 0于是 1 的位数被算成了 0整个结果直接乱掉。自查方法很简单从 n2 开始验证。n2 的正确答案是 6如果算出来是 5、4 或者别的数说明 len 相关逻辑肯定有问题。你也可以写几行打印把每一步的len、ans二进制形式和预期对照。bit_length类函数在不同语言里细节不同Python 的len(bin(i)) - 2也能用因为bin(i)返回的是0b...去掉前两位就是纯二进制位数。Java 的Integer.toBinaryString(i).length()也能用但会额外生成一个字符串不如numberOfLeadingZeros干净。C 的std::bit_width是 C20 才有的接口老项目不一定支持所以clz或者循环右移更稳。5.3 C / Java 的溢出与类型问题这是一个非常典型的线上 bug。有人把ans定义成int然后发现 n 稍微大一点结果就错了。原因在前面提过ans len在取模之前可能是一个很大的数早已超过 2^31 - 1。我算过一笔账每次循环前ans都小于10^9 7len最大是 17。所以ans len的最大值大约是(10^9 7) * 2^17 ≈ 1.31 × 10^14这个数仍然远小于 64 位整数的上限约9.22 × 10^18。所以只要ans是long long并且每步取模就绝对不会溢出。同理取i的补码后加法也不会造成问题。唯一要注意的是 Java 里long和 C 里long long都要用对别图省事写int。5.4 边界样例与验证方法做题时我的习惯是先跑几个小样例n期望输出检查点11循环起点是否正确26第一次遇到两个二进制位327拼接是否保持了高位顺序4220第一次遇到三位数12505379714验证取模逻辑如果这些样例全部通过基本可以确定核心逻辑正确。想要进一步确认可以用两个不同实现互相对拍比如一个用bit_length一个用连续段优化版本跑遍 1 到 10000 的随机 n断言输出完全一致。这种方法在算法题调试里非常实用。5.5 常见错误速查表症状可能原因解决办法n2 时结果不是 6len 计算不正确可能是 clz 少减了 1用32 - clz或改用 bit_length结果偶尔对偶尔差一点ans 类型用了 int中间溢出换成 long long / long结果整体偏大没在每步取模最后才取模把取模放进循环里n1 时结果不是 1循环从 0 开始算了一轮从 1 开始循环用字符串拼接方案跑到 n 大时卡死字符串 O(L^2) 拷贝改用位运算滚动拼接6. 从这道题延伸出去的二进制思维6.1 二进制运算在工程里的常见位置有人觉得位运算只是刷题用的和日常开发没关系实际上关系很大。数据封包和协议解析就是最典型的场景。比如你要把几个字段组成一个 32 位的整数4 位版本号、12 位头长度、16 位标识符代码里基本就是“左移 按位或”的组合。这和本题把 1 到 n 的二进制数拼接起来思路完全一致。文件格式和存储领域也随处可见。像 HDF5 这类容器格式里元数据用“属性”来存真正的二进制数据块则作为“数据集”存储。读取这些数据时你要处理大量按位排列的结构理解二进制拼接和移位能让你少踩很多解析上的坑。还有常见的 LRC 校验、CRC 校验。LRC 校验码的原理是把数据字节累加后取反加一最后得到的其实也是一个二进制数值CRC 更是直接在二进制多项式域上做除法本质上就是对二进制位的连续操作。你看这和题目里“二进制除法”“二进制计算”这些关键词是相通的。学好位运算不是只在 LeetCode 上有用。6.2 适合继续练的几道题如果你觉得这道题还没吃透我建议按这个顺序继续刷LeetCode 338. 比特位计数练习统计二进制中 1 的个数和位数计算关系密切。LeetCode 191. 位1的个数最经典的位操作题理解n (n - 1)的威力。LeetCode 1016. 子串能表示从 1 到 N 数字的二进制串和 1680 共用“连续二进制”背景但考察方向不同。LeetCode 剑指 Offer 15. 二进制中1的个数面试高频题考察位运算基本功。这几题做完你对二进制表示、移位、掩码、位计数这些概念会有更完整的认识。6.3 我的实操心得与避坑指南这道题我做了一遍之后最大的体会是遇到“拼接”类的问题先想清楚数学表达再想代码实现比直接上手调接口可靠得多。二进制世界里没有真正的“字符串拼接”只有左移、腾位、写入低位。你能不能用一句话把这道题描述成“每次把旧结果左移新数字的位数再把新数字放进去”决定了你能不能写出简洁且可扩展的代码。另外一个小技巧是写位运算代码时尽量用“打印二进制”来调试。C 里可以用bitset32Python 里直接bin(ans)Java 里用Integer.toBinaryString。很多自以为没问题的位运算打印出来一眼就能看出低位是不是被覆盖了高位是不是被截断了。最后再分享一个后续扩展方向如果你把 n 从 10^5 放大到 10^9逐项循环就不再可行这时候就需要用第 4 节提到的连续段公式做数学加速。我自己在准备面试时专门把这类“连续数字拼接”的问题整理成一组方便后面遇到类似题目时直接套用思路。你可以先掌握今天的滚动拼接写法熟悉之后再往数学优化方向深入。