Find a bit with no duplicates among multiple bits in Java

Question

I'm working on a project in java and I'm using bits to represent possible numbers. By giving each numbers a bit something like {2} would be 100 in binary aka 2^2 and {0,1,2} would be 111 in binary aka 2^2 + 2^1 + 2^0. I'm trying to find out whether there is a single bit that doesn't reoccur within several sets. example: from these sets {3,5,7}{3,5,9}{3,5,9}{1,5,6,9}{5,6,7,9}{3,7,9} I want to find {1} because it is the only one without duplicates

I have actually tried a similar problem in python and I also figured that if there is a way to do it using sets there is probably a way to do it using bits, but the way in which I did it was just brute force. You can technically just and all combinations(in my case 23) of 2 bits, then or them but I was kinda hoping for a faster method with less loops.

Answer 1

You can use two bitmasks, one tracking which bits have been seen at least once, and one tracking which bits have been seen more than once.

int atLeastOnce = 0;
int moreThanOnce = 0;
for (int i = 0; i < sets.length; i++) {
    moreThanOnce |= sets[i] & atLeastOnce;
    atLeastOnce |= sets[i];
}

After this, atLeastOnce & ~moreThanOnce gives a mask of the bits that were set exactly once. You can out whether there is any such bit by simply comparing that to zero, and you can get the index of the lowest element that occurs exactly once (if there is one) with Integer.numberOfTrailingZeros.