java - 面试编程问题？(长位表示)？

Question

给定一个长数 n，我们需要返回一个从 1 到 n 的二进制表示串联得到的长数？例如，假设 n=3，则答案为 27，因为二进制中的 1 为 01，2 为 10，3 为 11，因此串联后为 011011，即 27。这是我使用的方法，

class Solution {
    static String[] arr;

    public static long binaryArray(long A) {
        String res = "";
        for (long i = 1; i <= A; i++) {
            res += toBinary(i);
        }

        long rest = toLong(res);
        return rest % 1000000007;

    }

    static long toLong(String s) {
        int a = s.length();
        int pow = 0;
        long res = 0;
        for (int i = a - 1; i >= 0; i--) {
            char aa = s.charAt(i);
            long f = Character.getNumericValue(aa);
            long power = (long) Math.pow(2, pow);
            res += power * f;
            pow++;
        }
        return res;
    }

    static String toBinary(long a) {
        if (a == 0) {
            return "0";
        }
        String binary = "";
        binary = Long.toBinaryString(a);
        return binary;
    }

    public static void main(String args[]) {
        long n = 89900;
        arr = new String[(int) n + 1];
        arr[0] = "0";
        long startTime = System.nanoTime();
        long b = binaryArray(n);
        long endTime = System.nanoTime();
        long totalTime = endTime - startTime;
        long convert = TimeUnit.SECONDS.convert(totalTime, TimeUnit.NANOSECONDS);
        System.out.println(convert);
        System.out.println(b);

    }
}

但它没有在要求的时间内完成请求。有没有更快的方法？

Answer 1

public static long f(int n) {
    long n2 = ((long)n) << n;
    return n2 | n;
}

规范中有很多不相关的文本:二进制表示、串联等。说什么:

• n 的位应向左“连接”n 位 = 位移位。

所以这个面试问题是故意误导的，而实际的解决方案很简单。它尝试并成功地让受访者从位测试等开始。

现在我已经有点经验了，诀窍就是纵观全局，用集合或整数的位函数等概念来思考。

<小时/>

正如@kaya3评论的那样，以下内容可能更正确。

public static long f(int n) {
    long n2 = 0;
    for (int i = 0; i < n; ++i) {
        if ((n & (1 << i)) == 1) { // i'th bit set?
            int bits = 32 - Integer.numberOfLeadingZeros(i);
            n2 <<= bits;
            n2 |= i;
        }
    }
    return n2;
}