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

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)方法：

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()方法的情况下完成：

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;
}

^{1(方法numberOfLeadingZeros()是用@HotSpotIntrinsicCandidate注释的，所以使用本机解决方案可能会超快，这意味着这个Java代码替代方案可能不会更快。}

测试

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：

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));

输出

18: 15905522931971113522
19: 508976733823075632723
20: 16287255482338420247156
21: 521192175434829447909013
22: 16678149613914542333088438
23: 533700787645265354658830039
24: 17078425204648491349082561272
25: 546509606548751723170641960729
26: 17488307409560055141460542743354
27: 559625837105921764526737367787355
28: 17908026787389496464855595769195388
29: 573056857196463886875379064614252445
30: 18337819430286844380012130067656078270
31: 586810221769179020160388162164994504671
32: 37555854193227457290264842378559648298976
64: 471483835060474447584605138071473227083738554722043752192205889593231757234798071314332600270577600
128: 685385418402711161486992779215452480197156956593160845028648293349782283935659509581295718147533155031188929619519081596427609304635849304708531968190976802229890594798789934166770532152593884743090295308624351511929798643557538430848
256: 246422532279457970240939131862416256957912100676567284022182930350788567839691502682935548861928505318417306075544389639956672552326580169008528080129830322429712508593083839769096175727133924908330823876506697567963272081220317027757129623022363719594776044926884107531078136465754901556922215598679264299348040837049670711753684521748473384638643859758271742330378295219493243936419532611365679896772551640598210176805609455785828091793688653809020045393677303410807761070390084298154799431073337833749694111293934995919750974732669988765440

Answer 2

使用 StringBuilder 来包含二进制数。

要附加下一个数字的位，请使用最高一位的掩码 和带有掩码的值，将掩码向右移动 1 位，直到 0。

Say v = 1100
highest 1 bit is 1000

• v & 1000 = 1所以附加一个1
• v & 0100 = 1所以附加一个1
• v & 0010 = 0所以附加一个0
• v & 0001 = 0所以附加一个0

StringBuilder sb = new StringBuilder();

for (int i = 1; i < 15; i++) {
appendBinary(sb, i);
System.out.println(i + " : "
+ new BigInteger(sb.toString(), 2));
}
}

public static StringBuilder appendBinary(StringBuilder sb, int v) {
int mask = Integer.highestOneBit(v);
while (mask != 0) {
char bit = ((v & mask) == 0) ? '0' : '1';
sb.append(bit);
// In case v is negative.  Then mask will be negative.
// So shift accordingly.
mask >>>= 1;
}
// Convenience return.
// Same object as provided.
return sb;
}

指纹

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