BitSet是Java中专为位运算优化的高效数据结构，底层用long数组存储，仅支持非负整数，通过and()和or()原地执行CPU级位运算实现交并集，比哈希或Stream快10–100倍。
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 等更高级结构。
