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

Question

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

10

我正在尝试找到正确的方法来实现这个目标：

假设我们有一个位集合组如下：

我想测试哪些二进制位在所有的位集合中只被设置一次。例如，结果应该是：

由于第4位是所有系列中唯一只出现一次的位，因此进行按位逻辑操作的最佳方法是什么？

提前致谢。

- Dani C.

我非常好奇这个问题的最短答案。我可以想到几种方法来实现它，但我正在尝试构思一个一行代码的操作。 - John Willemse

1

如果你事先知道这个系列：转置它并寻找2的幂次方，那将指示只有1位被设置的列。 - Olivier Dulac

3个回答

4

您可以使用“一次两次”方法：

对于每个集合 - 对于每个元素 - 如果该元素在“一次”集合中 - 将其添加到“两次”集合中 - 否则 - 将其添加到“一次”集合中 - 返回“一次”集合减去“两次”集合

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

对于每个集合 C： - “两次” := “两次” OR (“一次” AND C) - “一次” := “一次” OR 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;

- John Dvorak

1

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

- Mohan Raj B

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- axtavt · Accepted Answer

你可以看到，你不能使用一个单独的集合来存储中间结果，因为你需要区分每个位的三种状态：从未设置、设置一次和设置多次。

因此，你至少需要两个中间结果。例如，你可以分别跟踪至少设置了一次和设置了多次的位：

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

或者使用BitSet（看起来不那么优雅，因为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;