java - 获取 BitSet 中设置位的所有索引

Question

我正在寻找一种快速算法，它可以为我提供 BitSet 对象中设置位的所有索引。这很慢：

BitSet bitSet = ...
Collection<Integer> indexes = new ArrayList<Integer>(bitSet.cardinality());
int nextSetBit = bitSet.nextSetBit(0);
for (int i = 0; i < bitSet.cardinality(); ++i ) {
    indexes.add(nextSetBit);
    nextSetBit = bitSet.nextSetBit(nextSetBit + 1);
}
...

任何帮助表示赞赏！

Answer 1

完全不需要使用bitSet.cardinality()：

for (int i = bitSet.nextSetBit(0); i != -1; i = bitSet.nextSetBit(i + 1)) {
    indexes.add(i);
}

Answer 2

在BitSet#nextSetBit(int) javadocs 中指定：

//To iterate over the true bits in a BitSet, use the following loop:
for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i+1)) {
     // operate on index i here
     if (i == Integer.MAX_VALUE) {
         break; // or (i+1) would overflow
     }
 }

Answer 3

从 Java 8 开始，您可以使用 BitSet 的stream()方法。

内部流流（）

返回此 BitSet 包含处于设置状态的位的索引流。

Answer 4

更改循环（您将复杂性增加到 O(N^2)，因为您在每次循环迭代中调用 cardinality()）：

for (int e = bitSet.cardinality(), i = 0; i < e; ++i ) {
    indexes.add(nextSetBit);
    nextSetBit = bitSet.nextSetBit(nextSetBit + 1);
}