在将long转换为二进制，然后将二进制字符串转换为long时获取运行时异常

Question

我正在HackerEarth平台上尝试此问题您会得到一个数字n。查找通过将前n个正整数的二进制表示连接起来而形成的数字的十进制值。

样本输入3

样本输出27（1：1，2：10，3：11，结果：11011）

我的解决方案：

public class test {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter wr = new PrintWriter(System.out);
        long n = Long.parseLong(br.readLine().trim());

        long out_ = FindBigNum(n);
        wr.println(out_);
        wr.close();
        br.close();
    }

    static long FindBigNum(long n) {
        // Write your code here
        String str = "";
        for (long i = 1; i <=n; i++) {
            str += Long.toBinaryString(i);
        }
        return Long.parseLong(str, 2);
    }
}

有人可以建议有效的方法吗？

Answer 1

如评论中所述，为获得更有效的解决方案，请使用<<位移运算符和Integer.numberOfLeadingZeros(i)方法：

Integer.numberOfLeadingZeros(i)

对于一个可能¹甚至更有效的解决方案，可以不用

static long binaryConcatRange(int n) {
    if (n < 0 || n > 17)
        throw new IllegalArgumentException("Out of range (0-17): " + n);
    long result = 0;
    for (int i = 1; i <= n; i++) {
        int bitLen = 32 - Integer.numberOfLeadingZeros(i);
        result = (result << bitLen) | i;
    }
    return result;
}

方法来完成：

numberOfLeadingZeros()

1]方法

static long binaryConcatRange(int n) {
    if (n < 0 || n > 17)
        throw new IllegalArgumentException("Out of range (0-17): " + n);
    long result = 0;
    for (int bitLen = 0, nextLenAt = 1, i = 1; i <= n; i++) {
        if (i == nextLenAt) {
            bitLen++;
            nextLenAt <<= 1;
        }
        result = (result << bitLen) | i;
    }
    return result;
}

被注释为numberOfLeadingZeros()，因此使用本机解决方案可能会很快，这意味着Java代码替代可能不会更快。

Test

@HotSpotIntrinsicCandidate

输出

for (int n = 0; n < 18; n++)
    System.out.printf("%s: %s%n", n, binaryConcatRange(n));

---

为了支持

0: 0
1: 1
2: 6
3: 27
4: 220
5: 1765
6: 14126
7: 113015
8: 1808248
9: 28931977
10: 462911642
11: 7406586283
12: 118505380540
13: 1896086088653
14: 30337377418462
15: 485398038695407
16: 15532737238253040
17: 497047591624097297

的值大于17，返回类型必须更改为n：

BigInteger

Test

static BigInteger binaryConcatRange(int n) {
    if (n < 0 || n == Integer.MAX_VALUE)
        throw new IllegalArgumentException("Out of range: " + n);
    BigInteger result = BigInteger.ZERO;
    for (int i = 1; i <= n; i++) {
        int bitLen = 32 - Integer.numberOfLeadingZeros(i);
        result = result.shiftLeft(bitLen).or(BigInteger.valueOf(i));
    }
    return result;
}

输出

for (int n = 18; n < 32; n++)
    System.out.printf("%s: %s%n", n, binaryConcatRange(n));
for (int n = 32; n <= 256; n *= 2)
    System.out.printf("%s: %s%n", n, binaryConcatRange(n));