我得到了一个巨大的位数组,保存为字节数组,它代表所有有符号 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 中会占用大量内存。
如何有效地多次迭代位数组中未设置的值?
最佳答案
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 位。
关于java - 在 Java 中有效地迭代大量位数组中未设置的值,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28752668/