Check if a bit is set only once in a series of bitsets

Question

I am trying to find the way what is the correct approach to achieve this: Imagine that we have a group of bit sets as following:

00100
00101
10000
00010
10001

I would like to test, which of the bits are only set once in all the bitsets. In the example, the result would be:

00010

since the 4th bit is the only one that appears only once in all series.

Which would be the best approach by doing bitwise logical operations?

Thanks in advance.

Answer 1

You can use the once-twice approach:

• for each collection
  • for each element
    • if the element is in the once set
      • add it to the twice set
    • else
      • add it to the once set
• return once - twice

The trick here is that it can be performed in parallel:

• for each collection C
  • twice := twice OR (once AND C)
  • once := once OR C

The implementation could look like:

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 2

As you can see you cannot do it using a single set for storing intermediate results, because you need to distinguish between 3 states for each bit: never set, set once and set more than once.

So, you need at least 2 intermediate results. For example, you can track bits set at least once and bits set more than once separately:

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

Or using BitSets (it looks not so elegant, because BitSet is not immutable):

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 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