java - 你能在 Java Bitset 中得到一组连续的位集吗？

Question

我有一个 BitSet，其中的信息如下所示:

00011110111110

是否有任何有效的方法来获取例如连续位集的最大数量？在上面的示例中，它将是 5。或者对位集的循环是否有效？我只是想知道是否有另一种更快的方法

Answer 1

对于 n 位的集合，有一个很好的算法，但它需要移位。或许可以使用 BitSet.toLongArray 和 valueOf(long[])。在不完整的代码中:

int maxNumberOfConsecutiveBits(BitSet bitSet) {
    int maxLength = 0;
    BitSet bs = bitSet.clone();
    while (!bs.isEmpty()) {
        ++maxLength;
        BitSet bs2 = shiftOne(bs);
        bs.and(bs2);
    }
    return maxLength;
}

while 循环将迭代到 maxLength。

使用 nextClearBit 遍历所有位 0 并且可能更快。

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

就我个人而言，我需要对这两种解决方案进行计时 - 以备不时之需。