在这里，我为这个问题提供了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;
}
}现在我有一个疑问，那就是当我们在for循环中的每一步进行调制时。在100000007之前，它不会影响结果，但在那之后，它将更改sum变量，并且这个循环将重复。为什么这个模不影响整体结果呢？提前谢谢。
1条答案
按热度按时间lbsnaicq1#
让我们看一个更简单的问题：取数字1000，写成位，然后取数字1001，写成位，把这两个连起来，那是什么，十进制的？
因此，答案是
1111 1010 0011 1110 1001，或1025001。但是，让我们对这个做一个更为数学化的理解：“连接两个”归结为：“将第一个数字中的位向左移动以留出足够的空间，然后添加第二个数字”。“左移x”与“乘2x”相同。就像我有一个数字“1234”，我告诉你把它左移两个点，这和乘以100是一样的：它变成123400，也就是1234*100，100就是102。所以，“左移x点”和“乘bx”是一样的，其中b是我们使用的数字系统的“基”；二进制为2，十进制为10。
因此，表述相同结果的另一种方式是：“取数字1000，乘以210，再加上1001。果然：
1000 * 2^10 + 1001确实是1025001。因此，你的算法中的一个“循环”是有效的：取我们到目前为止得到的结果，乘以2很多次（x次，其中x是我们处理这个循环的数字中最高1位的位置），然后加上新的数字。
所以，就是乘法和加法。
模的性质是对这些运算是稳定的。
考虑一下基础数学：你可能学过数字线。无限大的水平线。
一个模系统没有什么不同，除了数行是一个大循环。它是一个圆。在模100000007空间中，数字“5和6”与数字“0和1000000006”一样相邻。
在正常的数列上，
a * b = c，模的性质是，这也意味着(a%Z * b%Z)%Z = c%Z对于任何z。加法也是如此；如果a + b = c，那么(a%Z + b%Z)%Z = c%Z这也是事实。你可以试着用一堆数字来证明这一点，或者自己来证明这一点，或者在网上搜索这个属性的证明。例子：
因此：
你的问题归结为乘法和加法的许多应用。
乘法和加法可以毫无疑问地转化为模运算。
因此，您的算法是有效的。