连接前N个整数的二进制并返回十进制值 [英] concatenate binary of first N integers and return decimal value

问题描述

示例

N = 3 值 3 的第一个 N integers是1，2，3

N = 3 The first N integers for value 3 is 1, 2, 3

二进制

1是1

2是10

3是11

串联的 N = 3 个二进制值将为11011

Concatenations of N=3 of binary values will be 11011

对于二进制值11011返回的十进制值为27

And the decimal value returned for the binary value 11011 is 27

我在下面使用的代码仅适用于前整数 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);

对于更大的N个数，有关使用模10 ^ 9 + 7进行求解的任何想法(因为级联很大)

For larger N numbers, any ideas on solving using modulo 10^9 + 7 (since concatenation is large)

推荐答案

请注意，不需要使用字符串表示形式(此外，在任务更改后没有用).看一下按位算术的方法(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屋！