我正在寻找在任意位置提取任意长度（0 <= 长度 <= 16）的（无符号）位序列的最有效方法。骨架类显示了我当前的实现本质上是如何处理这个问题的：
public abstract class BitArray {
byte[] bytes = new byte[2048];
int bitGet;
public BitArray() {
}
public void readNextBlock(int initialBitGet, int count) {
// substitute for reading from an input stream
for (int i=(initialBitGet>>3); i<=count; ++i) {
bytes[i] = (byte) i;
}
prepareBitGet(initialBitGet, count);
}
public abstract void prepareBitGet(int initialBitGet, int count);
public abstract int getBits(int count);
static class Version0 extends BitArray {
public void prepareBitGet(int initialBitGet, int count) {
bitGet = initialBitGet;
}
public int getBits(int len) {
// intentionally gives meaningless result
bitGet += len;
return 0;
}
}
static class Version1 extends BitArray {
public void prepareBitGet(int initialBitGet, int count) {
bitGet = initialBitGet - 1;
}
public int getBits(int len) {
int byteIndex = bitGet;
bitGet = byteIndex + len;
int shift = 23 - (byteIndex & 7) - len;
int mask = (1 << len) - 1;
byteIndex >>= 3;
return (((bytes[byteIndex] << 16) |
((bytes[++byteIndex] & 0xFF) << 8) |
(bytes[++byteIndex] & 0xFF)) >> shift) & mask;
}
}
static class Version2 extends BitArray {
static final int[] mask = { 0x0, 0x1, 0x3, 0x7, 0xF, 0x1F, 0x3F, 0x7F, 0xFF,
0x1FF, 0x3FF, 0x7FF, 0xFFF, 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF };
public void prepareBitGet(int initialBitGet, int count) {
bitGet = initialBitGet;
}
public int getBits(int len) {
int offset = bitGet;
bitGet = offset + len;
int byteIndex = offset >> 3; // originally used /8
int bitIndex = offset & 7; // originally used %8
if ((bitIndex + len) > 16) {
return ((bytes[byteIndex] << 16 |
(bytes[byteIndex + 1] & 0xFF) << 8 |
(bytes[byteIndex + 2] & 0xFF)) >> (24 - bitIndex - len)) & mask[len];
} else if ((offset + len) > 8) {
return ((bytes[byteIndex] << 8 |
(bytes[byteIndex + 1] & 0xFF)) >> (16 - bitIndex - len)) & mask[len];
} else {
return (bytes[byteIndex] >> (8 - offset - len)) & mask[len];
}
}
}
static class Version3 extends BitArray {
int[] ints = new int[2048];
public void prepareBitGet(int initialBitGet, int count) {
bitGet = initialBitGet;
int put_i = (initialBitGet >> 3) - 1;
int get_i = put_i;
int buf;
buf = ((bytes[++get_i] & 0xFF) << 16) |
((bytes[++get_i] & 0xFF) << 8) |
(bytes[++get_i] & 0xFF);
do {
buf = (buf << 8) | (bytes[++get_i] & 0xFF);
ints[++put_i] = buf;
} while (get_i < count);
}
public int getBits(int len) {
int bit_idx = bitGet;
bitGet = bit_idx + len;
int shift = 32 - (bit_idx & 7) - len;
int mask = (1 << len) - 1;
int int_idx = bit_idx >> 3;
return (ints[int_idx] >> shift) & mask;
}
}
static class Version4 extends BitArray {
int[] ints = new int[1024];
public void prepareBitGet(int initialBitGet, int count) {
bitGet = initialBitGet;
int g = initialBitGet >> 3;
int p = (initialBitGet >> 4) - 1;
final byte[] b = bytes;
int t = (b[g] << 8) | (b[++g] & 0xFF);
final int[] i = ints;
do {
i[++p] = (t = (t << 16) | ((b[++g] & 0xFF) <<8) | (b[++g] & 0xFF));
} while (g < count);
}
public int getBits(final int len) {
final int i;
bitGet = (i = bitGet) + len;
return (ints[i >> 4] >> (32 - len - (i & 15))) & ((1 << len) - 1);
}
}
public void benchmark(String label) {
int checksum = 0;
readNextBlock(32, 1927);
long time = System.nanoTime();
for (int pass=1<<18; pass>0; --pass) {
prepareBitGet(32, 1927);
for (int i=2047; i>=0; --i) {
checksum += getBits(i & 15);
}
}
time = System.nanoTime() - time;
System.out.println(label+" took "+Math.round(time/1E6D)+" ms, checksum="+checksum);
try { // avoid having the console interfere with our next measurement
Thread.sleep(369);
} catch (InterruptedException e) {}
}
public static void main(String[] argv) {
BitArray test;
// for the sake of getting a little less influence from the OS for stable measurement
Thread.currentThread().setPriority(Thread.MAX_PRIORITY);
while (true) {
test = new Version0();
test.benchmark("no implementaion");
test = new Version1();
test.benchmark("Durandal's (original)");
test = new Version2();
test.benchmark("blitzpasta's (adapted)");
test = new Version3();
test.benchmark("MSN's (posted)");
test = new Version4();
test.benchmark("MSN's (half-buffer modification)");
System.out.println("--- next pass ---");
}
}
}
这可行，但我正在寻找更有效的解决方案（性能方面）。字节数组保证相对较小，在几个字节到最大 ~1800 字节之间。在每次调用 read 方法之间，该数组只被读取一次（完全）。getBits() 中不需要进行任何错误检查，例如超出数组等。
看来我上面最初的问题还不够清楚。N 位的“位序列”形成 N 位的整数，我需要以最小的开销提取这些整数。我对字符串没有用处，因为这些值要么用作查找索引，要么直接输入到某些计算中。所以基本上，上面显示的骨架是一个真实的类，getBits() 签名显示了其余代码如何与之交互。
将示例代码扩展为微基准，包括 blitzpasta 的解决方案（修复丢失的字节掩码）。在我的旧 AMD 机器上，结果显示为 ~11400ms 与 ~38000ms。仅供参考：它是杀死性能的除法和模运算。如果将/8替换为>>3并将%8替换为&7，则两种解决方案都非常接近（jdk1.7.0ea104）。
关于如何工作和做什么工作似乎有点混乱。示例代码的第一个原始帖子包含一个 read() 方法，用于指示字节缓冲区的填充位置和时间。当代码变成 microbench 时，这会丢失。我重新介绍了它以使这一点更清楚。这个想法是通过添加另一个需要实现 getBits() 和 prepareBitGet() 的 BitArray 子类来击败所有现有版本，后者可能是空的。不要更改基准测试来为您的解决方案提供优势，所有现有解决方案都可以这样做，这完全是一个没有实际意义的优化！（真的！！）
我添加了一个 Version0，它只会增加 bitGet 状态。它总是返回 0 以大致了解基准开销有多大。它只是为了比较。
此外，还添加了对 MSN 想法的改编（版本 3）。为了对所有竞争对手保持公平和可比性，字节数组填充现在是基准测试的一部分，也是一个准备步骤（见上文）。最初 MSN 的解决方案做得并不好，准备 int[] 缓冲区有很多开销。我冒昧地对这一步进行了一点优化，这使它变成了一个激烈的竞争对手:) 你可能还会发现我对你的代码进行了一些去复杂化。你的 getBit() 可以被压缩成一个 3-liner，可能会减少 1% 或 2%。我故意这样做是为了保持代码的可读性，并且因为其他版本也没有尽可能浓缩（再次为了可读性）。
结论（上面的代码示例更新为包含基于所有适用贡献的版本）。在我的旧 AMD 机器（Sun JRE 1.6.0_21）上，它们显示为：
V0 未实施耗时5384毫秒
V1 Durandal 的（原始）耗时10283毫秒
V2 blitzpasta（改编）耗时12212毫秒
V3 MSN（已发布）耗时11030毫秒
V4 MSN（半缓冲修改）耗时9700毫秒
注意：在这个基准测试中，每次调用 getBits() 平均获取 7.5 位，并且每个位只读取一次。由于 V3/V4 必须付出高昂的初始化成本，它们往往会表现出更好的运行时行为和更多、更短的提取（因此，平均提取大小越接近最大值 16 越差）。尽管如此，V4 在所有情况下都略微领先于其他所有方案。在实际应用中，必须考虑缓存争用，因为 V3/v4 所需的额外空间可能会增加缓存未命中率，从而使 V0 成为更好的选择。如果要多次遍历数组，则应优先考虑 V4，因为它的获取速度比其他任何方式都快，并且在第一次遍历后可以分摊昂贵的初始化。