获取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()方法。

IntStream 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);
}