bitset.andnot() 是 java 中实现集合差集 a−b 最高效的方式之一，通过位向量原地计算 bitseta & (~bitsetb)，时间复杂度约 o(n/64)，适用于非负整数且值域集中的场景。
在 Java 中，BitSet.andNot() 是实现集合差集（A − B）最高效的方式之一，特别适用于元素为非负整数且值域相对集中的场景。它直接操作位向量，时间复杂度接近 O(n/64)，远优于遍历或哈希集合的 O(n)。
理解 andNot() 的语义
bitSetA.andNot(bitSetB) 会**原地修改** bitSetA，将其更新为 bitSetA & (~bitSetB)，即保留 A 中存在但 B 中不存在的所有位。这正是集合差集 A − B 的位级定义。
- 要求 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 不接受负索引，若原始数据含负数，需做偏移映射（如全部加 maxAbsValue）
- 稀疏大值域效率下降：若 A 最大元素是 10⁷ 但只含 10 个数，BitSet 会分配约 1.25MB 内存，此时用 HashSet 更省空间
-
空值安全：b 为 null 会抛 NPE，建议判空：
if (b != null) a.andNot(b);
对比其他差集实现方式
与常见替代方案相比，BitSet.andNot() 在整数密集场景优势明显：
- HashSet.removeAll()：通用但涉及哈希计算和对象包装（Integer），GC 压力大
- Stream.filter().collect()：函数式写法清晰，但需遍历全部 A 元素并装箱，性能约为 BitSet 的 1/3～1/2
- Arrays / Collections 工具类：无原生差集方法，需手动实现，代码冗长且易出错
当处理上百万个 [0, 10⁵) 范围内的整数集合时，BitSet.andNot() 通常能在毫秒级完成差集计算。
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
