通过连接前 n 个自然数的二进制表示形成的数字的十进制值

问题描述

给定一个数n，找出由前n个自然数的二进制表示连接形成的数的十进制值.
打印答案模 10^9+7.

Given a number n, find the decimal value of the number formed by concatenating the binary representations of first n natural numbers.
Print answer modulo 10^9+7.

另外，n 可以大到 10^9，因此需要对数时间方法.

Also, n can be as big as 10^9 and hence logarithmic time approach is needed.

例如:n=4，答案 = 220

说明:数字形成=11011100 (1=1,2=10,3=11,4=100).11011100=220" 的十进制值.

Explanation: Number formed=11011100 (1=1,2=10,3=11,4=100). Decimal value of 11011100="220".

我在下面使用的代码仅适用于第一个整数 N<=15

The code I am using below only works for first integers N<=15

    String input = "";
    for(int i = 1;i<=n;i++) {
        input += (Integer.toBinaryString(i));
    }
    return Integer.parseInt(input,2);

推荐答案

请注意，使用字符串表示不是必需的(此外，在任务更改后没有用处).看按位算术的方法(Python，但原理是一样的)

Note that working with string representation is not necessary (moreover, is not useful after task changing). Look at approach with bitwise arithmetics (Python, but principle is the same)

有了关于模 1000000007 的新条件，我们只需在每一步的结果计算行中添加模运算，因为左移和 or-ing 相当于乘以 2 的幂再加，这些运算服从模的等价关系特性.注意中间结果不超过1000000007*n，所以long类型适合这里合理的n值.

With new condition concerning modulo 1000000007 we have just add modulo operation to result calculation line at every step, because shift left and or-ing is equivalent to multiplication by power of two and adding, these operations are obeyed to equivalence relations for modulo properties. Note that intermediate results don't exceed 1000000007*n, so long type is suitable here for reasonable n values.

n = 100  
size = 0   #bit length of addends
result = 0   # long accumulator
for i in range(1, n + 1):    
    if i & (i - 1) == 0:    #for powers of two we increase bit length
        size += 1
    result = ((result << size) | i) % 1000000007   #shift accumulator left and fill low bits with new addend
print(result)

没有按位运算的变体:

pow2 = 1
nextpow = 2
result = 0   # long accumulator
for i in range(1, n + 1):
    if i == nextpow:    #for powers of two we increase bit length
        pow2 = nextpow
        nextpow = nextpow * 2
    result = (result * pow2  + i) % 1000000007  #shift accumulator left and fill low bits with new addend

这篇关于通过连接前 n 个自然数的二进制表示形成的数字的十进制值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持跟版网！