java - 在 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

How can I efficiently iterate over this bit array?

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

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

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

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

How can I efficiently iterate multiple times over the not set values in the bit array?

在 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 位。