Get all indices of set bits in BitSet

Question

I am looking for a quick algorithm that gives me all the indices of the set bits in a BitSet object. This is slow:

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

Any help is appreciated!

Answer 1

No need to use bitSet.cardinality() at all:

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

Answer 2

As stated in 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

Change the loop (you increase the complexity to O (N ^ 2) because you call the power () in each iteration of the loop):

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