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

ループを変更します (各ループ反復で cardinality() を呼び出すため、複雑さを O(N^2) に増やします)。

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