连续二进制数的串联，模运算讨论行为

Question

这里我贡献了Java问题的解决方案。连续二进制数的串联：给定一个整数 n，return 通过按顺序连接 1 到 n 的二进制表示形式的二进制字符串的十进制值，模 10^9 + 7.

class Solution {
    public int concatenatedBinary(int n) {
        long sum = 0;
    
        for(int i = 1; i <= n; i++){
            sum = ((sum << Integer.toBinaryString(i).length()) + i) % 1000000007;
        }
    
        return (int) sum;
    }
}

现在我怀疑我们在 for 循环中的每一步都进行调制。直到 1000000007 才影响结果，但之后，它会改变 sum 变量，并重复这个循环。现在，为什么这个模数不影响整体结果？提前致谢。

Answer 1

我们看一个更简单的问题：取数字1000，写成位，然后取数字1001，写成位，将两者连接起来，那是什么，十进制？

1000 in bits is 11 1110 1000
1001 in bits is 11 1110 1001

因此，答案是 1111 1010 0011 1110 1001，或 1025001。

但是，让我们对此做更多的数学计算：“连接两个”归结为：“将第一个数字中的位向左移动以腾出足够的空间，然后添加第二个数字”。而“左移X”等同于'multiply by 2^X'。就像我有一个数字'1234'，我告诉你'shift that left by 2 spots'，它和乘以100是一样的：变成123400，也就是1234*100，而100就是10²。因此，'shift left by X spots' 与 'multiply by b^X' 相同，其中 b 是我们使用的数字系统的 'base'；二进制为 2，十进制为 10。

因此，表述相同结果的另一种方式是：'将数字 1000 乘以 2¹⁰，再加上 1001。果然：1000 * 2^10 + 1001确实是1025001.

因此，您的算法中的单个 'loop' 实际上是：将我们目前的结果乘以 2 多次（X 次，其中 X 是最高 1-位在我们正在处理这个循环的数字中），然后添加新数字。

所以，这只是乘法和加法。

Modulo 具有属性对于这些操作来说它是稳定的。

考虑基础数学：您可能学过数轴。一条水平线，无限大。

模数系统没有什么不同，除了数字线是一个大循环。这是一个圆圈。在模 1000000007 space 中，数字“5 和 6”与数字“0 和 1000000006”一样相邻。

给定，在正常数轴上，a * b = c，模有属性，这也意味着对于任何 Z，(a%Z * b%Z)%Z = c%Z。加法也是如此；如果 a + b = c，则 (a%Z + b%Z)%Z = c%Z 也成立。您可以尝试一堆数字并见证这一点，或者尝试自己证明这一点，或者在网上搜索证明这一点属性.

示例：

12 * 18 = 216
(12%7 * 18%7)%7 = 216%7
Yup, that checks out:
5 * 4 = 20
20%7 = 6.
216%7 is also 6.

因此：

你的问题归结为很多乘法和加法的应用。
乘法和加法毫无问题地转化为模数学。
因此，您的算法有效。

连续二进制数的串联，模运算讨论行为

Concatenation of Consecutive Binary Numbers, Modulo Operation discussion behavior

java

modulo

data-structures