有效地从byte[]数组中提取任意长度的位序列

我正在寻找在任意位置提取任意长度（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 ---");
    }
}
}

这有效，但我正在寻找一种更有效的解决方案（性能方面）。byte 数组保证相对较小，介于几个字节之间，最大值为 ~1800 字节。在每次调用 read 方法之间，数组只读取一次（完全）。在 getBits（） 中不需要任何错误检查，例如超出数组等。

看来我上面的最初问题还不够清楚。N位的“位序列”形成N位的整数，我需要以最小的开销提取这些整数。我对字符串没有用处，因为这些值要么用作查找索引，要么直接输入到一些计算中。所以基本上，上面显示的框架是一个真正的类，getBits（）签名显示了其余代码如何与它交互。

将示例代码扩展为微模板标记，包括闪电战的解决方案（修复了缺失的字节屏蔽）。在我的旧AMD盒子上，结果是~11400ms与~38000ms。仅供参考：它是杀死性能的除法和模运算。如果将 /8 替换为 >>3，将 %8 替换为 &7，则两种解决方案都非常接近 （jdk1.7.0ea104）。

对于如何以及要做什么似乎有点混乱。示例代码的第一个原始帖子包括一个 read（） 方法，用于指示字节缓冲区填充的位置和时间。当代码被转换为微板凳时，这就丢失了。我重新介绍了它，以使这一点更清晰一些。这个想法是通过添加另一个需要实现getBits（）和preparBitGet（）的BitArray子类来击败所有现有版本，后者可能是空的。不要改变基准测试来给你的解决方案带来优势，对所有现有的解决方案都可以做同样的事情，使这成为一个完全没有实际意义的优化！（真的！！）

我添加了一个版本0，它除了增加 bitGet 状态之外什么都不做。它始终返回 0，以便大致了解基准开销有多大。它只是为了比较。

此外，还添加了对MSN想法的改编（版本3）。为了保持所有竞争对手的公平性和可比性，字节数组填充现在是基准测试的一部分，也是一个准备步骤（见上文）。最初 MSN 的解决方案表现不佳，在准备 int[] 缓冲区时会产生很多开销。我冒昧地稍微优化了这一步，这使它成为一个激烈的竞争对手:)您可能还会发现我对您的代码进行了一些解扰。你的getBit（）可以浓缩成一个3行，可能会减少百分之一或百分之二。我故意这样做是为了保持代码的可读性，并且因为其他版本也没有尽可能压缩（同样是为了可读性）。

结论（上面的代码示例更新以包括基于所有适用贡献的版本）。在我的旧AMD盒子（Sun JRE 1.6.0_21）上，它们显示为：

V0 没有实现需要 5384 毫秒
V1 Durandal 的（原始）需要 10283 毫秒
V2 闪电战（改编）需要 12212 毫秒
V3 MSN（已发布）需要 11030 毫秒
V4 MSN（半缓冲修改）需要 9700 毫秒

注意：在此基准测试中，每次调用 getBits（） 平均获取 7.5 位，并且每个位仅读取一次。由于 V3/V4 必须支付高昂的初始化成本，因此它们往往会表现出更好的运行时行为，具有更多、更短的抓取时间（因此，最接近平均抓取大小的最大值为 16 时，情况会更糟）。尽管如此，V4在所有情况下都略微领先于所有其他场景。在实际应用程序中，必须考虑缓存争用，因为 V3/v4 所需的额外空间可能会将缓存未命中率增加到 V0 是更好选择的程度。如果要对数组进行多次遍历，则 V4 应该受到青睐，因为它的获取速度比其他数组都快，并且在第一次传递后摊销了代价高昂的初始化。