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取模这要求在递推过程中同步做模运算防止中间结果溢出。三个官方示例示例 1Input: n 1 Output: 1 Explanation: 1 in binary corresponds to the decimal value 1.示例 2Input: 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.示例 3Input: 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。有了递推式剩下的问题就集中在两点shift如何随着n的变化而变化递推过程中如何正确处理模运算。shift 的确定二进制位长与 2 的幂进位规律shift的取值不是固定的它等于当前n的二进制位数。而二进制位数只在跨过 2 的整数次幂时才会增加 1 位11→ 1 位210→ 2 位比 1 多 1 位311→ 2 位与 2 相同4100→ 3 位比 3 多 1 位7111→ 3 位与 6 相同81000→ 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 结合律 ((ab) % p c) % p (a (bc) % p) % p 5 ((a*b) % p * c)% p (a * (b*c) % p) % p 6 交换律 (a b) % p (ba) % 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^shiftf(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维护当前已拼接部分的十进制值初值为 0mod即模数100000000710^9 7shift记录当前i的二进制位数初值为 0循环内先用(i (i - 1)) 0判断i是否为 2 的整数次幂若是则shift加 1对应二进制位数增加随后执行递推核心res ((res shift) i) % mod把上一轮结果左移shift位加上i再取模循环结束返回res。以n 3手工推演一遍i是否 2 的幂shiftres1是1001(01)1 12是2102(12)2 63否32!02(62)3 27最终返回27与官方示例 2 一致。Go 实现二bits.Len 位长驱动第二种解法换了一个角度不再手动维护shift而是直接用标准库math/bits包中的bits.Len求当前数字的二进制位长// 解法二 位运算 func concatenatedBinary1(n int) int { res : 0 for i : 1; i n; i { res (resbits.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)位全为 0reslen | i等价于(reslen) 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 组测试数据n期望输出113271250537971442727837408243859510018181935729266627730462其中前 3 组对应官方示例后 4 组是仓库补充的随机边界用例。测试结构沿用本仓库统一的「para/ans数据对」风格para1680封装输入参数nans1680封装期望答案。测试函数会打印每组输入与concatenatedBinary的输出并同时调用concatenatedBinary1验证第二种实现两种实现在这些用例上输出一致互相印证正确性。运行方式与仓库其他题目一致在项目根目录执行go test ./leetcode/1680.Concatenation-of-Consecutive-Binary-Numbers/ -v -run Test_Problem1680若想覆盖整个仓库并生成覆盖率报告可参考根目录的 gotest.shgo test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...本仓库的 go.mod 声明了go 1.19及以上版本math/bits自 Go 1.9 起即为标准库两种解法不依赖任何第三方包可直接运行。总结LeetCode 1680 的解题脉络可以归纳为三步发现递推拼接即左移加数得到f(n) f(n-1) shift n确定 shift二进制位数只在 2 的整数次幂处加 1用(i (i-1)) 0判断或用bits.Len直接求位长同步取模利用模运算的加法分配律在每一步左移后立即取模既保证结果正确又防止溢出。这道题的价值在于把「二进制进位」「位移拼接」「模运算」三个基础主题串联成一个可复用的套路凡是「把多个数的二进制表示连接后求值」的题目都可以尝试转成「左移 加法 取模」的线性递推从而避免构造超长字符串。仓库中的双实现模拟 bits.Len为读者提供了从原理推导到标准库运用的完整对照样本。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
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取模这要求在递推过程中同步做模运算防止中间结果溢出。三个官方示例示例 1Input: n 1 Output: 1 Explanation: 1 in binary corresponds to the decimal value 1.示例 2Input: 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.示例 3Input: 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。有了递推式剩下的问题就集中在两点shift如何随着n的变化而变化递推过程中如何正确处理模运算。shift 的确定二进制位长与 2 的幂进位规律shift的取值不是固定的它等于当前n的二进制位数。而二进制位数只在跨过 2 的整数次幂时才会增加 1 位11→ 1 位210→ 2 位比 1 多 1 位311→ 2 位与 2 相同4100→ 3 位比 3 多 1 位7111→ 3 位与 6 相同81000→ 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 结合律 ((ab) % p c) % p (a (bc) % p) % p 5 ((a*b) % p * c)% p (a * (b*c) % p) % p 6 交换律 (a b) % p (ba) % 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^shiftf(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维护当前已拼接部分的十进制值初值为 0mod即模数100000000710^9 7shift记录当前i的二进制位数初值为 0循环内先用(i (i - 1)) 0判断i是否为 2 的整数次幂若是则shift加 1对应二进制位数增加随后执行递推核心res ((res shift) i) % mod把上一轮结果左移shift位加上i再取模循环结束返回res。以n 3手工推演一遍i是否 2 的幂shiftres1是1001(01)1 12是2102(12)2 63否32!02(62)3 27最终返回27与官方示例 2 一致。Go 实现二bits.Len 位长驱动第二种解法换了一个角度不再手动维护shift而是直接用标准库math/bits包中的bits.Len求当前数字的二进制位长// 解法二 位运算 func concatenatedBinary1(n int) int { res : 0 for i : 1; i n; i { res (resbits.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)位全为 0reslen | i等价于(reslen) 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 组测试数据n期望输出113271250537971442727837408243859510018181935729266627730462其中前 3 组对应官方示例后 4 组是仓库补充的随机边界用例。测试结构沿用本仓库统一的「para/ans数据对」风格para1680封装输入参数nans1680封装期望答案。测试函数会打印每组输入与concatenatedBinary的输出并同时调用concatenatedBinary1验证第二种实现两种实现在这些用例上输出一致互相印证正确性。运行方式与仓库其他题目一致在项目根目录执行go test ./leetcode/1680.Concatenation-of-Consecutive-Binary-Numbers/ -v -run Test_Problem1680若想覆盖整个仓库并生成覆盖率报告可参考根目录的 gotest.shgo test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...本仓库的 go.mod 声明了go 1.19及以上版本math/bits自 Go 1.9 起即为标准库两种解法不依赖任何第三方包可直接运行。总结LeetCode 1680 的解题脉络可以归纳为三步发现递推拼接即左移加数得到f(n) f(n-1) shift n确定 shift二进制位数只在 2 的整数次幂处加 1用(i (i-1)) 0判断或用bits.Len直接求位长同步取模利用模运算的加法分配律在每一步左移后立即取模既保证结果正确又防止溢出。这道题的价值在于把「二进制进位」「位移拼接」「模运算」三个基础主题串联成一个可复用的套路凡是「把多个数的二进制表示连接后求值」的题目都可以尝试转成「左移 加法 取模」的线性递推从而避免构造超长字符串。仓库中的双实现模拟 bits.Len为读者提供了从原理推导到标准库运用的完整对照样本。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
