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$和$b$的二进制拼接，结果等于$a\times 10^{bit_len(b)} + b$，而乘法和加法均满足模运算的分配律，所以从$1$到$n$一次遍历不断拼接相邻两个整数并不断取模即可。

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

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

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

AC代码

C++

/*
 * @LastEditTime: 2026-02-28 10:15:41
 */
typedef long long ll;
const ll MOD = 1e9 + 7;

class Solution {
public:
    int concatenatedBinary(int n) {
        ll ans = 0;
        for (int i = 1; i <= n; i++) {
            ans = ((ans << (32 - __builtin_clz(i))) + i) % MOD;
        }
        return ans;
    }
};

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

千篇源码题解已开源