java - 创建 BitSet 的组合

Question

假设我有一个 Java BitSet。我现在需要对 BitSet 进行组合，以便只有设置的位才能翻转。即只需要设置的位的组合。

对于例如。位集 - 1010，组合 - 1010、1000、0010、0000

位集 - 1100，组合 - 1100、1000、0100、0000

我可以想到一些解决方案我可以采用所有 4 位的组合，然后将组合与原始位集进行异或。但对于大型稀疏 BitSet 来说，这将非常消耗资源。所以我一直在寻找更优雅的解决方案。

Answer 1

您似乎想要获取 power set位组的值。已经有答案here关于如何获取 Set<T> 的幂集。在这里，我将展示该文章中所示算法的修改版本，使用 BitSet s:

private static Set<BitSet> powerset(BitSet set) {
    Set<BitSet> sets = new HashSet<>();
    if (set.isEmpty()) {
        sets.add(new BitSet(0));
        return sets;
    }
    Integer head = set.nextSetBit(0);
    BitSet rest = set.get(0, set.size());
    rest.clear(head);
    for (BitSet s : powerset(rest)) {
        BitSet newSet = s.get(0, s.size());
        newSet.set(head);
        sets.add(newSet);
        sets.add(s);
    }
    return sets;
}