BitSet高效操作：快速实现数组交并集运算

BitSet是Java中专为位运算优化的高性能数据结构，通过底层long数组实现非负整数集合的紧凑存储与CPU级原生位操作，使交集（and）和并集（or）运算比传统哈希或Stream快10–100倍，尤其在百万级、值域集中且稀疏度低的场景下优势惊人；它天然去重、内存可控（最大值建议≤10⁷），但需规避逐个set的低效初始化、原地修改陷阱及全量遍历开销——掌握clone安全调用、nextSetBit高效转数组和valueOf批量加载等技巧，才能真正释放其极致性能。

BitSet 是 Java 中专为位运算优化的高效数据结构，特别适合处理大规模整数集合（尤其是值域集中、稀疏度低的场景）。用 and() 和 or() 实现交集与并集，本质是底层的批量位运算（CPU 级别 AND/OR 指令），比遍历、哈希或 Stream 流快 10–100 倍，尤其在百万级整数集合上优势明显。

前提：数据必须是非负整数且范围可控

BitSet 底层用 long 数组存储，索引即整数值。因此：

• 只支持 非负整数（0, 1, 2, …），负数会抛出 IndexOutOfBoundsException
• 最大值不宜过大（如 ≤ 10⁷ 较稳妥），否则 BitSet 占用内存显著增加（约 maxValue / 8 字节）
• 若原始数组含重复值，BitSet 自动去重，天然适配集合语义

快速构建 BitSet（避免逐个 set）

不要用 for 循环调用 set(i) —— 这是 O(n) 次方法调用开销。应先排序+去重，再用批量方式初始化：

// 示例：从 int[] arr 构建 BitSet
Arrays.sort(arr);
BitSet bs = new BitSet();
int prev = -1;
for (int x : arr) {
    if (x != prev && x >= 0) {
        bs.set(x); // 仍需 set，但跳过重复，且已排序利于 CPU 缓存
        prev = x;
    }
}

更进一步：若数据来自文件或数据库且可预知范围，可用 BitSet.valueOf(long[]) 直接加载位块（需自行将整数映射为位偏移）。

交集（and）与并集（or）的正确用法

注意：and() 和 or() 是**原地修改**操作，不返回新 BitSet。常用安全模式如下：

• 交集：拷贝一个副本再 and
  BitSet intersection = (BitSet) bs1.clone(); intersection.and(bs2);
• 并集：拷贝后 or，或直接用 or（若允许修改 bs1）
  BitSet union = (BitSet) bs1.clone(); union.or(bs2);

错误写法：bs1.and(bs2) 会把 bs1 改成交集结果，原 bs1 丢失 —— 若后续还需用原 bs1，务必 clone。

结果转回数组（按需，避免全遍历）

BitSet 提供 nextSetBit(fromIndex)，可高效遍历所有置位索引，时间复杂度正比于结果集大小，而非整个位域：

public static int[] toIntArray(BitSet bs) {
    int size = bs.cardinality(); // 先获知元素个数，避免扩容
    int[] arr = new int[size];
    int idx = 0, i = bs.nextSetBit(0);
    while (i != -1) {
        arr[idx++] = i;
        i = bs.nextSetBit(i + 1);
    }
    return arr;
}

若只需前 N 个交集结果（如 Top-K），可提前 break；若只要判断是否为空交集，用 isEmpty() 比遍历快得多。

不复杂但容易忽略：BitSet 的极致性能依赖“整数 → 位索引”的零成本映射。一旦数据需哈希、字符串转换或跨类型比较，就该换用 LongAdder + 并行流或 RoaringBitmap 等更高级结构。

到这里，我们也就讲完了《BitSet高效操作：快速实现数组交并集运算》的内容了。个人认为，基础知识的学习和巩固，是为了更好的将其运用到项目中，欢迎关注golang学习网公众号，带你了解更多关于的知识点！