For sets of n bits there is a nice algorithm but it requires a shift of bits. Maybe doable with BitSet.toLongArray
and valueOf(long[])
. In incomplete code:
int maxNumberOfConsecutiveBits(BitSet bitSet) {
int maxLength = 0;
BitSet bs = bitSet.clone();
while (!bs.isEmpty()) {
++maxLength;
BitSet bs2 = shiftOne(bs);
bs.and(bs2);
}
return maxLength;
}
The while loop will iterate upto maxLength.
Using nextClearBit
iterates through all bits 0 and might be faster.
int maxNumberOfConsecutiveBits(BitSet bs) {
int maxLength = 0;
int onesI = bs.length(); // Points to the prior 0.
for (int i = onesI; (i = bs.previousClearBit(i - 1)) >= 0; ) {
int length = onesI - 1 - i;
maxLength = Math.max(maxLength, length);
i = bs.previousSetBit(i - 1) + 1; // Heuristic, optional.
onesI = i;
}
return maxLength;
}
Personally I would need to time both solutions - for surprises.