通过合并前n个自然数的二进制表示形式形成的数字的十进制值 [英] decimal value of the number formed by concatenating the binary representations of first n natural numbers

问题描述

给出一个数字 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

Eg: n=4, Answer = 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的新条件下，我们仅在每一步向结果计算行添加了模运算，因为左移和或运算等于乘以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个自然数的二进制表示形式形成的数字的十进制值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！