在 Java 中有效地迭代大量位数组中未设置的值

Question

我得到了一个保存为字节数组的巨大位数组，它代表所有有符号 int 值（4,294,967,295）。

byte[] bitArray = byte[536870912];

数组中的每个字节代表 8 个数字，每一位代表一个数字。这意味着 byte[0] 存储 1, 2, 3, 4, 5, 6, 7, 8，而 byte[1] 存储 9, 10, 11, 12, 13, 14, 15, 16 等。

我用它来存储一个巨大的表，我可以在其中将数字设置为 true 或 false（0 或 1）。我有一些相当有效的方法来检查是否设置了一个位并设置了一个位（仅使用按位运算符）。

现在我需要一遍又一遍地迭代这个表来找到设置为 0 的位。当然，只存储我想要迭代的数字会相当有效，所以我不需要每次都检查它们，但是数字太多，将它们存储在 ArrayList 中会占用大量内存。

如何有效地多次迭代位数组中未设置的值？

Answer 1

如何有效地迭代这个位数组？

实现此目的的一种方法是使用 BitSet。这将一次扫描long[]64 位，但其底层方法被转换为内在函数。即单机器代码指令可能比用 Java 编写的任何指令都要快。

如果你真的想自己写这个，我建议你看看 BitSet 是如何工作的并复制它的代码。（或者使用BitSet）

我建议您查看 Long 的numberOfLeadingZeros(long) numberOfTrailingZeros(long) bitCount(long)方法

内在函数是 JVM“识别”并用专门的机器代码指令替换的方法，这可以使其比复制代码并在 Java 中运行相同的代码快得多。

如何有效地多次迭代位数组中未设置的值？

在 BitSet 中它使用以下循环

public int nextSetBit(int fromIndex) {
    if (fromIndex < 0)
        throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);

    checkInvariants();

    int u = wordIndex(fromIndex);
    if (u >= wordsInUse)
        return -1;

    long word = words[u] & (WORD_MASK << fromIndex);

    while (true) {
        if (word != 0)
            return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word);
        if (++u == wordsInUse)
            return -1;
        word = words[u];
    }
}

注意：这是在每次迭代中检查 64 位。