如何在 Java 中利用 BitSet.andNot() 实现集合间的差集运算以快速筛选出不属于 B 的 A 元素

说到集合差集运算（A − B），Ja va 里最趁手的一个工具就是 BitSet.andNot()。它直接操作位向量，时间复杂度接近 O(n/64)，比起遍历或者哈希集合那种 O(n) 的方式，效率上完全是两个量级。尤其适合元素是非负整数、且值域比较集中的场景——说白了，就是整数范围不大、但数量很多的情况。

一句话总结：bitSetA.andNot(bitSetB) 会原地修改 bitSetA，把它更新成 bitSetA & (~bitSetB)——也就是保留 A 里有、B 里没有的那些位。这不正是集合差集 A − B 的位级定义吗？

理解 andNot() 的语义

使用前有几个基本前提：A 和 B 的元素都必须是非负整数（BitSet 下标从 0 开始）。如果 A 包含某个整数 x，那 bitSetA.set(x) 就得是 true；B 同理。万一 x 超过了当前 BitSet 的容量，set() 会自动扩容，不用操心。

标准差集操作步骤

拿一个具体例子来说明：A = {1, 3, 5, 7}，B = {3, 5, 8}，求 A − B，结果应该是 {1, 7}。操作起来就几步：

• 创建两个 BitSet：BitSet a = new BitSet(); BitSet b = new BitSet();
• 填数据：a.set(1); a.set(3); a.set(5); a.set(7);，b.set(3); b.set(5); b.set(8);
• 执行差集：a.andNot(b); —— 这一下，a 里就只剩下位置 1 和 7 是 true 了
• 提取结果：可以用 a.stream().toArray() 拿到数组，或者 a.stream().forEach(System.out::println) 直接打印

注意事项与常见陷阱

BitSet 差集虽然看起来简单，但有几个细节一不留神就容易踩坑：

• 不可逆操作：andNot() 会直接修改原 BitSet。如果想保留原始的 A，记得先调用 clone()：BitSet result = (BitSet) a.clone(); result.andNot(b);
• 负数不支持：BitSet 不接受负索引。如果原始数据里混了负数，就得做偏移映射——比如把所有数加上一个足够大的偏移量，确保都变成非负。
• 稀疏大值域效率下降：假设 A 的最大元素是 10⁷，但实际只存了 10 个数，那 BitSet 会分配大约 1.25MB 的内存。这时候用 HashSet 反而更省空间。
• 空值安全：如果 b 是 null，andNot() 会抛出 NPE。稳妥的做法是先判个空：if (b != null) a.andNot(b);

对比其他差集实现方式

跟其他常用方案比一下，BitSet.andNot() 在整数密集场景下的优势非常明显：

• HashSet.removeAll()：通用性强，但涉及到哈希计算和 Integer 对象包装，GC 压力不小。
• Stream.filter().collect()：代码写起来很函数式、很清晰，但需要遍历全部 A 元素再装箱，性能大致是 BitSet 的 1/3 到 1/2。
• Arrays / Collections 工具类：压根没有原生差集方法，得自己实现，代码又长又容易出 bug。

在实际场景中，如果手头有上百万个范围在 [0, 10⁵) 内的整数集合，用 BitSet.andNot() 通常能在毫秒级把差集算完，这速度相当可观。