🔗 初学者友好指南 ‘连续二进制数的拼接’ - Problem 1680 (C++, Python, JavaScript)

Source: Dev.to

问题概述

给定内容：
一个整数 n，表示从 1 到 n 的数字范围。

目标：
按顺序将该范围内每个数字的二进制表示连接起来。将得到的二进制字符串再转换回十进制整数，并返回其对 (10^9 + 7) 的模。

直觉：移位的艺术

为了解决此问题而不实际生成巨大的字符串（这会慢且占用大量内存），我们使用位运算。

对于从 1 到 n 的每个数字 i：

1. 求位长： 确定表示 i 所需的位数。
   例子：2 的二进制是 10，需要 2 位。
2. 左移结果： 将当前累计值左移相应的位数，为新值腾出“槽位”。
3. 使用 OR 合并： 用按位或运算把 i 的二进制位放入新槽位。
4. 保持数值小： 在每一步都对 (10^9 + 7) 取模，以防溢出。

步骤演示：理解示例

当 n = 3 时：

最终二进制 11011 等于十进制的 27。

C++ 解法

#include 

class Solution {
public:
    const int mod = 1e9 + 7;

    int concatenatedBinary(int n) {
        long result = 0;
        for (int i = 1; i (result);
    }
};

Python 解法

class Solution:
    def concatenatedBinary(self, n: int) -> int:
        mod = 10**9 + 7
        result = 0

        for i in range(1, n + 1):
            # bit_length() gives the number of bits required for the integer
            width = i.bit_length()
            # Shift result left by width and add the current number i
            result = ((result << width) | i) % mod

        return result

JavaScript 解法

/**
 * @param {number} n
 * @return {number}
 */
var concatenatedBinary = function(n) {
    const mod = 1000000007n;
    let result = 0n;

    for (let i = 1; i <= n; i++) {
        // Find bit length by converting to binary string
        let width = BigInt(i.toString(2).length);
        // Using BigInt to handle large numbers before modulo
        result = ((result << width) | BigInt(i)) % mod;
    }

    return Number(result);
};

关键要点

• 位移运算： 左移 k 位相当于将数字乘以 (2^k)。
• 模运算： 在每一步都取模可以让数值保持在数据类型的安全范围内。
• 效率： 计算位宽并使用位运算的速度远快于字符串拼接再转换的做法。

最后思考

本题展示了“低层次”思考如何带来高性能解法。在实际场景中，这类概念对 数据压缩 和 网络协议 至关重要，因为信息需要被压缩到尽可能小的位空间以节省带宽。掌握位运算逻辑会让你在靠近硬件或优化高并发系统时更加得心应手。