5

我正在使用 BitSets 在 Java 中实现一个程序，但我陷入了以下操作：

给定 N 个 BitSet，如果所有 BitSet 中有超过 1 个，则返回 0，否则返回 1

例如，假设我们有这 3 个集合：

  • 10010
  • 01011

  • 00111

  • 11100 预期结果

对于以下套装：

  • 10010
  • 01011
  • 00111
  • 10100

  • 00101

  • 01000 预期结果

我正在尝试通过按位操作来进行排他，并且我已经意识到我需要的实际上是所有集合之间的排他或，但不是以迭代的方式，所以我很困惑该怎么做。这甚至可能吗？

我想避免昂贵的解决方案，即必须检查每组中的每一位，并为每个位置保留一个计数器......

谢谢你的帮助

编辑：正如一些人所问的，这是我正在从事的项目的一部分。我正在构建一个时间表生成器，基本上其中一个软约束是没有学生应该在 1 天内只有 1 节课，所以这些集合代表每小时参加的学生，我想过滤那些只有 1 节课的学生.

4

2 回答 2

4

你可以用两个值做你想做的事。一个位至少设置一次，第二个位设置不止一次。该组合可用于确定那些设置一次且不再重复。

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'));

印刷

01000
于 2012-04-30T18:42:30.427 回答
1

首先，如果不检查每组中的每一位，您就无法做到这一点。如果您可以在不检查任意位的情况下解决这个问题，那么这意味着存在两种解决方案（即，该位可以是两个值中的每一个都有两个不同的解决方案）。

如果您想要一种更有效的方式来计算多个位集的 XOR，我会考虑将您的集合表示为整数而不是单个位的集合。然后只需将整数异或在一起即可得出您的答案。否则，在我看来，您将不得不遍历每一位，检查其值并自行计算解决方案（如您在问题中所述）。

于 2012-04-30T18:05:32.010 回答