LeetCode 1680.连接连续二进制数字：O(n)左移位运算

【LetMeFly】1680.连接连续二进制数字：O(n)左移位运算

力扣题目链接：https://leetcode.cn/problems/concatenation-of-consecutive-binary-numbers/

给你一个整数n，请你将1到n的二进制表示连接起来，并返回连接结果对应的十进制数字对109+ 7取余的结果。

示例 1：

输入：n = 1输出：1解释：二进制的 "1" 对应着十进制的 1 。

示例 2：

输入：n = 3输出：27解释：二进制下，1，2 和 3 分别对应 "1" ，"10" 和 "11" 。 将它们依次连接，我们得到 "11011" ，对应着十进制的 27 。

示例 3：

输入：n = 12输出：505379714解释：连接结果为 "1101110010111011110001001101010111100" 。 对应的十进制数字为 118505380540 。 对 109+ 7 取余后，结果为 505379714 。

提示：

• 1 <= n <= 105

解题方法：位运算

将a aa和b bb的二进制拼接，结果等于a × 10 b i t _ l e n ( b ) + b a\times 10^{bit\_len(b)} + ba×10bit_len(b)+b，而乘法和加法对于取模运算都是幂等的，所以从1 11到n nn一次遍历不断拼接相邻两个整数并不断取模即可。

如何求得一个整数的二进制长度？

很多编程语言都有库函数，例如C++可以使用__builtin_clz求得一个整数二进制下前导零的个数，32位整数的位数32 3232减去前导零的个数就是这个数二进制的长度。

• 时间复杂度O ( n ) O(n)O(n)。大多数现代架构会把__builtin_clz直接映射为单条硬件指令，单次执行时间复杂度是O ( 1 ) O(1)O(1)
• 空间复杂度O ( 1 ) O(1)O(1)

AC代码

C++

/* * @LastEditTime: 2026-02-28 10:15:41 */typedeflonglongll;constll MOD=1e9+7;classSolution{public:intconcatenatedBinary(intn){ll ans=0;for(inti=1;i<=n;i++){ans=((ans<<(32-__builtin_clz(i)))+i)%MOD;}returnans;}};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源