我已经在业余时间参加了面试街挑战赛"改变比特"一周多一点了，现在我只是在旋转我的轮子，所以我希望有人能给我一个正确的方向。
挑战的基础是采用两位字符串A&B，并运行许多操作这两个位字符串的查询。
设A和B是两个N比特数。你得到了A和B的初始值，你应该编写一个程序来处理三种查询：
- set_a idx x：将a[idx]设置为x，其中0<=idx<N、 其中A[idx]为idx为A的最低有效位
- set_b idx x：将b[idx]设置为x，其中0<=idx<N
- get_c idx：打印c[idx]，其中c=A+B，0<idx
其中，比特数的长度为1到100000，并且程序可以具有1到500000个set_a、set_b或get_c的任何组合的查询。
为了尽量减少循环，我使用C作为运行总数。当a或B中的一个比特改变时，改变的比特也从C中相加或相减。当加法和相减时，在仍然有进位比特的情况下从改变的比特向左手进行进一步最小化循环。
private static void add(final boolean[] the_array, final int the_index)
{
for(int iter = the_array.length - the_index - 1; iter >= 0; iter--)
{
if(the_array[iter])
{
the_array[iter] = false;
}
else if(!the_array[iter])
{
the_array[iter] = true;
return ;
}
}
}
private static void subtract(final boolean[] the_array, final int the_index)
{
for(int iter = the_array.length - the_index - 1; iter >= 0; iter--)
{
if(the_array[iter])
{
the_array[iter] = false;
return ;
}
else if(!the_array[iter])
{
the_array[iter] = true;
}
}
}
总的来说，该程序运行得很好，完成了比特长度为100000和500000的最坏边缘情况，查询运行时间约为120ms，但它仍然不够快，无法应对挑战。由于位长度的大小很快超过了Java中的基元整数值（也很长），因此大多数API不适用于此。由于我没有取得太大进展，增加总体运行时大小开始表明，可能有一种算法或数据结构比阵列更适合这一点。有什么想法吗？
嗯，在我的脑海中：
不要让C一直在附近/更新，只需快速计算你需要的比特即可。请记住，当你添加A和B的相应位位置时，你只需要向下看相邻的低有效位，直到你找到它们都为零的点——任何超过这一点的东西都不能携带比特通过。例如
A: 001101001010111
B: 010110100010110
^ asked for C there
1000111^ only need to add bits from here
^ until you get your answer.
我会使用long[]而不是boolean[]。每个长有64位，您可以执行组合操作，如
if (the_array[iter] == -1L) // all 1s
the_array[iter] = 0L; // all zeros.
您可以在与布尔运算大致相同的时间内执行64位运算，使循环速度提高64倍。
BTW：在大多数JVM中，使用boolean[]将使用long[]的8倍内存，因为每个boolean使用一个字节的内存。
使用较长类型存储数据的示例。
- BitSet使用
long[]来存储其位。http://fuseyism.com/classpath/doc/java/util/BitSet-source.html - BigInteger使用
int[]来存储其位。http://developer.classpath.org/doc/java/math/BigInteger-source.html
根据您正在执行的操作，使用int可能更容易工作，例如x = (long) a * b会溢出long，但不会溢出int。
如果您正在扫描大量的位（正如BitSet可以做的那样），那么使用long[]可以更快。
添加一个基准，显示它可以产生的时间差异。
public static final int RUNS = 100;
public static void main(String... args) throws InterruptedException {
boolean[] bools = new boolean[1024 * 1024];
long[] longs = new long[bools.length / 64];
for (int i = 0; i < 5; i++) {
testBools(bools);
testLongs(longs);
}
}
private static void testBools(boolean[] bools) {
long start = System.nanoTime();
for (int t = 0; t < RUNS; t++) {
// set all to true
for (int i = 0; i < bools.length; i++)
bools[i] = true;
// search for a false;
for (boolean b : bools)
if (!b) throw new AssertionError();
// set all to false
for (int i = 0; i < bools.length; i++)
bools[i] = false;
// search for a true;
for (boolean b : bools)
if (b) throw new AssertionError();
}
long time = System.nanoTime() - start;
System.out.printf("To set and scan a boolean[] with %,d bits took %,d us%n",
bools.length, time / 2/ RUNS / 1000);
}
private static void testLongs(long[] longs) {
long start = System.nanoTime();
for (int t = 0; t < RUNS; t++) {
// set all to true
for (int i = 0; i < longs.length; i++)
longs[i] = ~0; // all 1s
// search for a false;
for (long l : longs)
if (l != ~0) throw new AssertionError();
// set all to false
for (int i = 0; i < longs.length; i++)
longs[i] = 0; // all 0s
// search for a true;
for (long l : longs)
if (l != 0) throw new AssertionError();
}
long time = System.nanoTime() - start;
System.out.printf("To set and scan a long[] with %,d bits took %,d us%n",
longs.length * Long.SIZE, time / 2/ RUNS / 1000);
}
打印
To set and scan a boolean[] with 1,048,576 bits took 777 us
To set and scan a long[] with 1,048,576 bits took 104 us
To set and scan a boolean[] with 1,048,576 bits took 666 us
To set and scan a long[] with 1,048,576 bits took 20 us
To set and scan a boolean[] with 1,048,576 bits took 537 us
To set and scan a long[] with 1,048,576 bits took 18 us
To set and scan a boolean[] with 1,048,576 bits took 567 us
To set and scan a long[] with 1,048,576 bits took 28 us
To set and scan a boolean[] with 1,048,576 bits took 776 us
To set and scan a long[] with 1,048,576 bits took 27 us
在本例中，与long[] 相比，使用boolean[]大约慢30倍