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

Question

这里我为这个问题提供Java解决方案。连续二进制数的连接：给定一个整数n，返回二进制字符串的十进制值，该字符串由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;
}
}

现在我有一个疑问，那就是当我们在循环中的每一步都进行调制时。它在1000000007之前不会影响结果，但在那之后，它将更改总和变量，并且此循环将重复。现在，为什么这个模不影响整体结果？提前谢谢。

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"；与"乘以2^X"相同。就像我有一个数字"1234"，我告诉你"左移2个点"，这和乘以100是一样的：这就变成了123400，也就是1234*100，100只是10²。因此，"X点左移"与"乘以b^X"相同，其中b是我们使用的数字系统的"基数"；二进制为2，十进制为10。

因此，一种不同的方法来陈述相同的结果："取数字1000，乘以2¹⁰，再加1001。果不其然：1000 * 2^10 + 1001确实是1025001。"。

因此，算法中的单个"循环"是有效的：取我们迄今为止的结果，将其乘以2多次(X次，其中X是我们处理该循环的数字中最高1位的位置(，然后添加新数字。

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

Modulo的特性是，它对这些操作是稳定的。

考虑一下基本数学：你可能被教过关于数字线的知识。一条无限大的水平线。

模系统也没什么不同，只是数字线是一个大循环。这是一个圆圈。在模1000000007空间中，数字"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.

因此：

1. 您的问题可以归结为乘法和加法的许多应用
2. 乘法和加法可以毫无问题地转换为模数学
3. 因此，您的算法有效