检查在一系列位集中是否只设置了一位

Question

我试图找到实现这一目标的正确方法:想象一下,我们有一组位集如下:

00100
00101
10000
00010
10001

我想测试一下,哪些位只在所有位集中设置一次.在示例中,结果将是:

00010

因为第4位是唯一一个在所有系列中只出现一次的位.

通过按位逻辑运算,哪种方法最好？

提前致谢.

Answer 1

正如您所看到的,您无法使用单个集合来存储中间结果,因为您需要区分每个位的3个状态:从不设置,设置一次并设置多次.

因此,您至少需要2个中间结果.例如,您可以跟踪至少设置一次的位和分别设置多次的位:

int atLeastOnce = 0;
int moreThanOnce = 0;
for (int current: sets) {
    moreThanOnce |= (atLeastOnce & current);
    atLeastOnce |= current;
}
int justOnce = atLeastOnce & ~moreThanOnce;

或者使用BitSets(它看起来不那么优雅,因为BitSet它不是不可变的):

BitSet atLeastOnce = new BitSet();
BitSet moreThanOnce = new BitSet();
for (BitSet current: sets) {
    BitSet moreThanOnceInCurrent = (BitSet) atLeastOnce.clone();
    moreThanOnceInCurrent.and(current);
    moreThanOnce.or(moreThanOnceInCurrent);
    atLeastOnce.or(current);
}
atLeastOnce.andNot(moreThanOnce);
BitSet justOnce = atLeastOnce;

Answer 2

您可以使用一次两次的方法：

• 对于每个集合
  • 对于每个元素
    • 如果该元素在集合once中
      • 将其添加到twice集合中
    • 别的
      • 将其添加到once集合中
• 返回once-twice

这里的技巧是它可以并行执行：

• 对于每个集合C
  • twice:=twice或（once与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;