Exclusive or between N bit sets

Question

I am implementing a program in Java using BitSets and I am stuck in the following operation:

Given N BitSets return a BitSet with 0 if there is more than 1 one in all the BitSets, and 1 otherwise

As an example, suppose we have this 3 sets:

• 10010
• 01011

• 00111

• 11100 expected result

For the following sets :

• 10010
• 01011
• 00111
• 10100

• 00101

• 01000 expected result

I am trying to do this exclusive with bit wise operations, and I have realized that what I need is literally the exclusive or between all the sets, but not in an iterative fashion, so I am quite stumped with what to do. Is this even possible?

I wanted to avoid the costly solution of having to check each bit in each set, and keep a counter for each position...

Thanks for any help

Edit : as some people asked, this is part of a project I'm working on. I am building a time table generator and basically one of the soft constraints is that no student should have only 1 class in 1 day, so those Sets represent the attending students in each hour, and I want to filter the ones who have only 1 class.

Answer 1

You can do what you want with two values. One has the bits set at least once, the second has those set more than once. The combination can be used to determine those set once and no more.

int[] ints = {0b10010, 0b01011, 0b00111, 0b10100, 0b00101};
int setOnce = 0, setMore = 0;
for (int i : ints) {
    setMore |= setOnce & i;
    setOnce |= i;
}
int result = setOnce & ~setMore;
System.out.println(String.format("%5s", Integer.toBinaryString(result)).replace(' ', '0'));

prints

01000