Can you get a set of consecutive bits set in Java Bitset?

Question

I have a BitSet and the info in it looks like this:

00011110111110

Is there any efficient method to get for example max number of continuous bits set? In the example above it would be 5. Or is a loop over the bit set efficient? I am just wondering if there is a another faster way

Answer 1

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.

Answer 2

Proposed Algorithm:

Suppose we are in the middle of a BitSet, as of yet our longest run is 5. We encounter our next 1. We can then skip four slots ahead.

• If the skipped to slot has a 1, we continue until we get a 0. Then, we backtrack from our original skip spot and see if the run continues. If the run is less than max, do nothing. If not, we set max run to the length of the run. Then, in either case, we change our next position to after the 0.
• If the skipped to slot has a 0, we know that any run before this cannot be the max run.
• Repeat the above steps.

This is of course best case sublinear and worst case equivalent to looping the the list exactly once, as we are never checking a slot more than once.