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

bit-manipulation

Solution

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;

Problem

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.

Original source