LeetCode-Go 题解 | 1680. Concatenation of Consecutive Binary Numbers：递推公式与位运算取模实现

LeetCode-Go 题解 | 1680. Concatenation of Consecutive Binary Numbers：递推公式与位运算取模实现

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

导读

LeetCode 1680「连接连续二进制数字」要求把1到n的二进制表示按顺序首尾相连，再求这个长二进制串对应的十进制数值（对10^9 + 7取模）。它把「二进制进位规律」「位运算左移」「模运算分配律」三个知识点揉进了一道看似简单的模拟题中。本文基于 LeetCode-Go 仓库中 题目 README 的解题思路与源码，完整推导递推公式f(n) = f(n-1) << shift + n，逐行讲解仓库给出的「模拟左移」与「bits.Len位长驱动」两种 Go 实现，并结合测试文件说明如何运行与验证。读完本文，你将掌握一类「边拼接、边取模」的位运算题的通用套路。

题目原文与题意拆解

Given an integern, return thedecimal valueof the binary string formed by concatenating the binary representations of1tonin order,modulo10^9 + 7.

题面虽然只有一句话，但隐藏了两个关键点：一是拼接后的二进制串长度可能非常大（n最大为10^5，此时二进制串总长度可达约1.5 × 10^6位），无法直接构造出完整整数；二是结果需要对10^9 + 7取模，这要求在递推过程中同步做模运算，防止中间结果溢出。

三个官方示例

示例 1：

Input: n = 1 Output: 1 Explanation: "1" in binary corresponds to the decimal value 1.

示例 2：

Input: n = 3 Output: 27 Explanation: In binary, 1, 2, and 3 corresponds to "1", "10", and "11". After concatenating them, we have "11011", which corresponds to the decimal value 27.

示例 3：

Input: n = 12 Output: 505379714 Explanation: The concatenation results in "1101110010111011110001001101010111100". The decimal value of that is 118505380540. After modulo 10^9 + 7, the result is 505379714.

示例 3 最能说明问题：1到12拼接后的二进制串"1101110010111011110001001101010111100"对应的十进制整数是118505380540，远超 32 位整数范围，必须一边累加一边取模。

数据约束

• 1 <= n <= 10^5

这意味着输入规模允许O(n)的线性扫描，但绝不允许用字符串拼接后逐位转换的朴素做法——串长可达百万位级别，构造字符串本身就会超时超内存。

核心递推：f(n) = f(n-1) << shift + n

本题的正解在于发现拼接过程与「左移 + 加法」的等价关系。假设f(n)表示把1到n的二进制串连接后得到的十进制数值，那么把n的二进制表示接到f(n-1)后面，等价于：

f(n) = f(n-1) << shift + n

其中shift是n的二进制表示的长度（位数）。例如n = 3时，3的二进制是"11"，长度为 2，所以：

f(3) = f(2) << 2 + 3 = 6 << 2 + 3 = 24 + 3 = 27

与示例 2 完全吻合。这个公式的本质是：把已有的结果整体左移shift位，腾出低shift位空间，再用加法（或按位或）把n填进去。仓库 README 中给出的正是这个递推式：f(n) = f(n-1) << shift + n。

有了递推式，剩下的问题就集中在两点：

1. shift如何随着n的变化而变化；
2. 递推过程中如何正确处理模运算。

shift 的确定：二进制位长与 2 的幂进位规律

shift的取值不是固定的，它等于当前n的二进制位数。而二进制位数只在跨过 2 的整数次幂时才会增加 1 位：

• 1（"1"）→ 1 位
• 2（"10"）→ 2 位，比 1 多 1 位
• 3（"11"）→ 2 位，与 2 相同
• 4（"100"）→ 3 位，比 3 多 1 位
• 7（"111"）→ 3 位，与 6 相同
• 8（"1000"）→ 4 位，比 7 多 1 位

也就是说，只有当i恰好是 2 的整数次幂时，shift才需要自增 1。仓库源码利用了一个经典位运算技巧来判断 2 的幂：

if (i & (i - 1)) == 0 { shift++ }

i & (i-1)会把i二进制中最右侧的 1 消掉。若结果为 0，说明i的二进制中只有一个 1，即i是 2 的整数次幂。以i = 4为例：4 & 3 = 100 & 011 = 0，判定成立，shift从 2 增至 3。

这条规律也被称作「二进制进位规律」，是理解本解法的时间线关键：shift随i单调不减，且只在 2 的幂处跳变。

模运算规则与防溢出处理

由于最终结果要对10^9 + 7取模，递推过程中的每一步都必须同步取模。这里用到的是模运算的基本法则，仓库 README 完整列出了常用公式：

模运算与基本四则运算有些相似，但是除法例外。 (a + b) % p = (a % p + b % p) % p （1） (a - b) % p = (a % p - b % p) % p （2） (a * b) % p = (a % p * b % p) % p （3） a ^ b % p = ((a % p)^b) % p （4） 结合律： ((a+b) % p + c) % p = (a + (b+c) % p) % p （5） ((a*b) % p * c)% p = (a * (b*c) % p) % p （6） 交换律： (a + b) % p = (b+a) % p （7） (a * b) % p = (b * a) % p （8） 分配律： ((a +b)% p * c) % p = ((a * c) % p + (b * c) % p) % p （9）

本题实际用到的是**加法运算法则（公式 1）**与乘法的结合：

f(n) % p = ((f(n-1) << shift) % p + n % p) % p

由于左移在数值上等价于乘以2^shift，f(n-1) << shift可能迅速膨胀，所以源码中的做法是对每一步的结果整体取模：

res = ((res << shift) + i) % mod

在 Go 中，int在 64 位平台上是 64 位整数，而n最大为10^5，其二进制位数不超过 17 位；res在每一步取模后始终小于10^9 + 7，因此res << shift最多约10^9 × 2^17 ≈ 1.3 × 10^14，远在 64 位整数范围内，不会溢出。这也是为什么可以在循环体内安全地「先左移、后取模」。

Go 实现一：模拟左移 + 2 的幂判定

仓库中的第一种解法（见 源码文件）严格遵循递推公式：

package leetcode import ( "math/bits" ) // 解法一 模拟 func concatenatedBinary(n int) int { res, mod, shift := 0, 1000000007, 0 for i := 1; i <= n; i++ { if (i & (i - 1)) == 0 { shift++ } res = ((res << shift) + i) % mod } return res }

逐行解读：

• res维护当前已拼接部分的十进制值，初值为 0；
• mod即模数1000000007（10^9 + 7）；
• shift记录当前i的二进制位数，初值为 0；
• 循环内先用(i & (i - 1)) == 0判断i是否为 2 的整数次幂，若是则shift加 1（对应二进制位数增加）；
• 随后执行递推核心res = ((res << shift) + i) % mod：把上一轮结果左移shift位，加上i，再取模；
• 循环结束返回res。

以n = 3手工推演一遍：

最终返回27，与官方示例 2 一致。

Go 实现二：bits.Len 位长驱动

第二种解法换了一个角度：不再手动维护shift，而是直接用标准库math/bits包中的bits.Len求当前数字的二进制位长：

// 解法二 位运算 func concatenatedBinary1(n int) int { res := 0 for i := 1; i <= n; i++ { res = (res<<bits.Len(uint(i)) | i) % (1e9 + 7) } return res }

bits.Len(uint(i))返回i从最高位 1 起算的二进制位数，例如bits.Len(1)=1、bits.Len(2)=2、bits.Len(3)=2、bits.Len(4)=3，与解法一中维护的shift完全等价。拼接操作改用按位或|：由于左移后低bits.Len(i)位全为 0，res<<len | i等价于(res<<len) + i，且不会产生进位冲突。模数写作浮点字面量1e9 + 7，其值同样是1000000007。

两种解法在时间复杂度和结果上完全一致，区别仅在于：

• 解法一：用(i & (i-1)) == 0判 2 的幂，只做常数次位运算；
• 解法二：用bits.Len直接求位长，语义更直白，代码更短。

从源码结构看，解法一是「手动推演进位」的模拟派，解法二是「借助标准库」的简洁派，二者互为印证，适合对照学习。

复杂度分析

• 时间复杂度：O(n)，循环从1遍历到n，每次迭代只做常数次位运算与一次取模，n ≤ 10^5时轻松通过；
• 空间复杂度：O(1)，仅使用常数个变量，不构造任何字符串或数组。

相比「拼接字符串再转整数」的朴素做法（时间O(L)、空间O(L)，其中L为拼接后二进制串总长度，可达约1.5 × 10^6），递推位运算方案在时间、空间上都是最优的。

测试用例与运行验证

仓库为本题提供了完整的单元测试文件 1680. Concatenation of Consecutive Binary Numbers_test.go，包含 7 组测试数据：

其中前 3 组对应官方示例，后 4 组是仓库补充的随机边界用例。测试结构沿用本仓库统一的「para/ans数据对」风格：para1680封装输入参数n，ans1680封装期望答案。测试函数会打印每组输入与concatenatedBinary的输出，并同时调用concatenatedBinary1验证第二种实现（两种实现在这些用例上输出一致，互相印证正确性）。

运行方式与仓库其他题目一致，在项目根目录执行：

go test ./leetcode/1680.Concatenation-of-Consecutive-Binary-Numbers/ -v -run Test_Problem1680

若想覆盖整个仓库并生成覆盖率报告，可参考根目录的 gotest.sh：

go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...

本仓库的 go.mod 声明了go 1.19及以上版本，math/bits自 Go 1.9 起即为标准库，两种解法不依赖任何第三方包，可直接运行。

总结

LeetCode 1680 的解题脉络可以归纳为三步：

1. 发现递推：拼接即左移加数，得到f(n) = f(n-1) << shift + n；
2. 确定 shift：二进制位数只在 2 的整数次幂处加 1，用(i & (i-1)) == 0判断，或用bits.Len直接求位长；
3. 同步取模：利用模运算的加法分配律，在每一步左移后立即取模，既保证结果正确又防止溢出。

这道题的价值在于把「二进制进位」「位移拼接」「模运算」三个基础主题串联成一个可复用的套路：凡是「把多个数的二进制表示连接后求值」的题目，都可以尝试转成「左移 + 加法 + 取模」的线性递推，从而避免构造超长字符串。仓库中的双实现（模拟 +bits.Len）为读者提供了从原理推导到标准库运用的完整对照样本。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go