CODEWITHSUNDEEP
bit-manipulation
Dani C.
Dani C.

Reputation: 920

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

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.

Upvotes: 10

Views: 250

Answers (3)

axtavt
axtavt

Reputation: 242686

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;

Upvotes: 11

Mohan Raj B
Mohan Raj B

Reputation: 1026

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

Upvotes: 1

John Dvorak
John Dvorak

Reputation: 27277

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;

Upvotes: 4

Related Questions