bit-manipulation - 检查一系列位集中是否只设置了一次

Question

我正在尝试找到实现此目标的正确方法的方法:
想象一下，我们有一组位集，如下所示:

00100
00101
10000
00010
10001

我想测试一下，哪些位在所有位集中仅设置了一次。在该示例中，结果将是:

00010

因为第4位是在所有系列中仅出现一次的唯一位。

进行按位逻辑运算的最佳方法是哪一种？

提前致谢。

Answer 1

您可以使用两次方法:

每个集合

每个元素

(如果元素位于once集中)

将它添加到twice集合

中

else

将它添加到once集合

中

返回once-twice

这里的技巧是可以并行执行:

每个集合

C

twice:= twice或(once AND C)

once:= once或C

该实现可能如下所示:

BitSet once = new BitSet();
BitSet twice = new BitSet();
for(BitSet b : sets){
  BitSet mask = (BitSet) b.clone();
  mask.and(once);
  twice.or(mask);
  once.or(b);
}
once.andNot(twice);
return once;