M1680.连接连续二进制数字

bit manipulation, https://leetcode.cn/problems/concatenation-of-consecutive-binary-numbers/

给你一个整数 n ，请你将 1 到 n 的二进制表示连接起来，并返回连接结果对应的 十进制 数字对 10^9 + 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 <= 10^5

class Solution:
    def concatenatedBinary(self, n: int) -> int:
        s = ''
        for i in range(1, n+1):
            s += bin(i)[2:]
        
        return int(s, 2) % (10**9 + 7)

这道题要求我们将从 $1$ 到 $n$ 的所有整数的二进制表示连接起来，并将结果对 ${10}^9+7$ 取余。

算法思路

对于每一个数字 $i$，当我们将其二进制表示拼接到当前的结果 $ans$ 后面时，相当于将当前的 $ans$ 向左移动 $i$ 的二进制长度，然后再把 $i$ 加上去。 也就是说：ans = ((ans << length) | i) % MOD

我们不需要对每个数都去计算它的二进制长度，因为一个数的二进制长度 length 只有在遇到 $2$ 的幂（即 $1,2,4,8,16,\dots$）时才会增加 $1$。 判断一个数 $i$ 是否是 $2$ 的幂，可以使用非常经典的位运算技巧：i & (i - 1) == 0。如果条件成立，说明 $i$ 是 $2$ 的幂，我们将 length 增加 $1$。

这样，我们就可以在一个 $O(n)$ 的循环中以极小的常数完成所有运算。

Python 3 代码

class Solution:
    def concatenatedBinary(self, n: int) -> int:
        MOD = 10**9 + 7
        ans = 0
        length = 0
        
        for i in range(1, n + 1):
            # 当 i 是 2 的幂时，其二进制长度增加 1
            if i & (i - 1) == 0:
                length += 1
            
            # 将当前结果左移 length 位，并加上当前的数字 i（由于左移后低位全为0，可以使用按位或 | 代替加法 +）
            ans = ((ans << length) | i) % MOD
            
        return ans

复杂度分析

• 时间复杂度: $O(n)$，我们只需要从 $1$ 遍历到 $n$，每一步只进行基础的位运算、加法以及取余等常数时间的操作，对于 $n\le {10}^5$ 的数据量可以在几毫秒内执行完毕。
• 空间复杂度: $O(1)$，仅使用了几个变量来记录当前长度、余数等信息，不需要额外的存储空间。