bit-manipulation - 检查一个位是否在一系列位集中仅设置一次

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;

Answer 3

int length = 5;
int count[] = new int[length];
for (i = 0; i < bitset.length(); i++) {   
    int value = bitset[i];
    unsigned int count = 0;

    for (int j = 0; j < length; j++) {           // until all bits are zero
        if ((value & 1) == 1)     // check lower bit
            count[j]++;
        value >>= 1;              // shift bits, removing lower bit
    }
}

int number = 00000;
for (int k = 0; k < 5; k++) {
    if (count[k] == 1) 
         number = number | 1; 
    number >>= 1;
}

number is desired answer