Java中查找多个位中不重复的位

Question

我正在用java开发一个项目，我使用位来表示可能的数字，比如{2}在二进制中是100，又称为4，而{0,1,2}在二进制中是111，又称为7。我我试图找出是否有一个位在几组中不会重复出现。 例子： 来自这些集合 {3,5,7}{3,5,9}{3,5,9}{1,5,6,9}{5,6,7,9}{3,7,9} 我想找到 {1}，因为它是唯一一个没有重复项的

我实际上在Python中尝试过类似的问题，并且我还认为，如果有一种方法可以使用集合来完成它，那么可能有一种方法可以使用位来完成它，但我这样做的方式只是蛮力。从技术上讲，您可以仅 和 2 位的所有组合（在我的例子中为 23），然后 或 它们，但我有点希望有一种更快的方法，循环更少。

Answer 1

您可以使用两个位掩码，一个跟踪哪些位至少被看到一次，另一个跟踪哪些位被多次看到。

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

在此之后，

atLeastOnce & ~moreThanOnce

给出了仅设置一次的位的掩码。只需将其与零进行比较，您就可以知道是否存在任何这样的位，并且您可以通过

Integer.numberOfTrailingZeros

获得仅出现一次（如果有）的最低元素的索引。