Java中如何快速检测多个BitSet（位向量）是否存在交集？

Great question! Your core goal is to check if there's at least one bit position that's set to 1 in all your BitSet vectors. Let's break down the issues with your current approach and explore more efficient solutions.

First, I noticed a small mistake in your code: you wrote check.add(bitVecs[i]), but that's an OR operation—what you actually need here is check.and(bitVecs[i]) to compute the intersection of the current check set with the next bit vector. Without fixing this, your logic won't work correctly.

Your original approach (fixing the AND operation) works, but it has room for optimization. The problem with repeatedly calling and() is that it modifies the check BitSet every time, and for large BitSets, this involves iterating through all the underlying long values. While BitSet.intersects() is faster than and() for pairwise checks, it can't directly solve the "all vectors share a common bit" problem—since pairwise intersections don't guarantee a global intersection (e.g., A∩B≠∅, B∩C≠∅ doesn't mean A∩B∩C≠∅).

Option 1: Optimized Stepwise Intersection with Early Termination #

We can enhance your original approach by leveraging intersects() to avoid unnecessary and() operations. Here's how:

1. Start with a copy of the first BitSet (instead of a full set of 1s—this reduces the initial size of the check set).
2. For each subsequent BitSet:
   • First, use intersects() to check if there's any overlap with the current intersection set. If not, return false immediately.
   • If there is overlap, update the check set with and() to keep only the common bits.

This way, we skip the costly and() operation entirely when we know there's no overlap.

public static boolean hasCommonBitOptimizedStepwise(BitSet[] bitVecs) {
    if (bitVecs == null || bitVecs.length == 0) {
        return false;
    }

    // Start with the first vector's bits as our initial intersection set
    BitSet currentIntersection = (BitSet) bitVecs[0].clone();

    for (int i = 1; i < bitVecs.length; i++) {
        BitSet nextVec = bitVecs[i];
        // Early exit if no overlap exists between current intersection and next vector
        if (!currentIntersection.intersects(nextVec)) {
            return false;
        }
        // Update intersection to only keep bits common to both
        currentIntersection.and(nextVec);
    }

    return !currentIntersection.isEmpty();
}

Option 2: Targeted Check Using the Smallest BitSet #

A more efficient approach (especially when one of your BitSets has very few set bits) is to focus only on the bits that are set in the smallest BitSet. Here's the logic:

1. Find the BitSet with the fewest set bits (since this gives us the least number of candidate positions to check).
2. If this smallest BitSet is empty, return false immediately (no bits can be common).
3. For each bit position set in the smallest BitSet, check if all other BitSets have that bit set.
4. If we find such a position, return true; if none are found, return false.

This avoids modifying entire BitSets and instead only checks the most likely candidate positions.

public static boolean hasCommonBitSmallestFirst(BitSet[] bitVecs) {
    if (bitVecs == null || bitVecs.length == 0) {
        return false;
    }

    // Find the BitSet with the fewest set bits (minimizes candidate checks)
    BitSet smallestBitSet = bitVecs[0];
    int minCardinality = smallestBitSet.cardinality();

    for (BitSet vec : bitVecs) {
        int cardinality = vec.cardinality();
        if (cardinality == 0) {
            return false; // Empty vector can't share a common bit
        }
        if (cardinality < minCardinality) {
            minCardinality = cardinality;
            smallestBitSet = vec;
        }
    }

    // Check each set bit in the smallest BitSet against all other vectors
    int pos = smallestBitSet.nextSetBit(0);
    while (pos != -1) {
        boolean allHaveBit = true;
        for (BitSet vec : bitVecs) {
            if (!vec.get(pos)) {
                allHaveBit = false;
                break;
            }
        }
        if (allHaveBit) {
            return true;
        }
        pos = smallestBitSet.nextSetBit(pos + 1);
    }

    return false;
}

Which Option to Choose? #

• Use Option 1 when most of your BitSets have a large number of set bits, or when the size of the BitSet (number of bits) is small. The stepwise intersection leverages bulk operations on the underlying long arrays, which are fast for dense sets.
• Use Option 2 when at least one BitSet has a small number of set bits. For example, if one vector only has 5 bits set, you'll only need to check 5 positions instead of iterating through entire BitSets repeatedly.

内容的提问来源于stack exchange，提问作者Mark Jin