Java: BitSet比较

Question

假设我们有两个Java中的BitSet对象，其值为：

//<MSB....LSB>
B1:<11000101>
B2:<10111101>

如何比较B1和B2以确定B1表示的值是否大于B2所表示的值。

BitSet中的逻辑运算符(>，<，==)是否被重载？还是我需要编写自己的实现？

更新：刚刚发现"The operator > is undefined for the argument type(s) java.util.BitSet, java.util.BitSet"。有没有内置方法可以实现这一点？

- Mangat Rai Modi

---

Java 中没有运算符重载。您可以编写函数或使用预定义的接口，如 Comparable。 - Adem

Answer 1

你可以通过对两个集合进行xor运算，并将结果的length与位集长度进行比较来实现:

• 如果xor为空，则位集相等。您可以通过调用equals()绕过此操作。
• 否则，xor结果的长度将等于两个值之间不同的最高有效位的位置。
• 拥有此位设置的两个操作数中的任何一个都是两个中较大的那一个。

这是一个示例实现：

int compare(BitSet lhs, BitSet rhs) {
    if (lhs.equals(rhs)) return 0;
    BitSet xor = (BitSet)lhs.clone();
    xor.xor(rhs);
    int firstDifferent = xor.length()-1;
    if(firstDifferent==-1)
            return 0;

    return rhs.get(firstDifferent) ? 1 : -1;
}

演示。

- Sergey Kalinichenko

---

我的错，我理解了逻辑。它非常出色。 - Mangat Rai Modi

@MangatRai 在这里更加显著的是 xor 被实现为一种破坏性操作，改变返回类型对此并没有帮助。 - Marko Topolnik

有趣的想法，我认为使用length()是很棒的，但是我找到了一个反例，表明实现是有问题的：ideone.com/hCJZ1q -- "a"不能小于"b"，而"b"又小于"a" -- 所有你的例子都只设置了一个位。 - stivlo

@stivlo 感谢您发现这个错误！我已经修复了实现以解决这个问题。 - Sergey Kalinichenko

完美，它工作了！非常好和紧凑。XOR 给出第一个不同的位，因此 lhs 和 rhs 将具有该位的不同值，您可以使用该信息来提供唯一的排序。太棒了。 - stivlo

Answer 2

不，操作符没有被重载，因为a）Java中没有操作符重载，b）你期望的是错误和不合逻辑的。

BitSet就像其名称所示“一组位”。你不能告诉一个“更大”和“更小”的集合——这就像说一种颜色比另一种颜色“更大”。如果您想要比较位集，则必须创建一个比较度量标准——我认为您想比较从位创建的整数值——如果是这种情况，请使用例如BitSet to and from integer/long中的代码，然后调用

static int compare( BitSet bs1, BitSet bs2 ) {
  return Long.compare(Bits.convert(bs1),Bits.convert(bs2));
}

或者，作为一个Comparator，

class BitSetComparator implements Comparator<BitSet> {
  int compare( BitSet bs1, BitSet bs2 ) {
    return Long.compare(Bits.convert(bs1),Bits.convert(bs2));
  }
}

请注意，在这种特殊情况下，两个集合都必须适合于long（最多63位）。或者，假设您的度量标准是“具有更高无符号整数表示的集合较大”，则可以使用XOR运算，或循环遍历位，或任何其他遍历所有位的结构。

int compare( BitSet bs1, BitSet bs2 ) {
  BitSet x = ((BitSet)bs1.clone()).xor(bs2);
  return ( x.isEmpty() ) ? 0 : ( x.length() == bs2.length() ? 1 : -1 );
}

但在所有这些情况下，如果您的目标是比较位，则最好使用long存储数据，然后将其直接作为无符号值进行比较，使用https://docs.oracle.com/javase/8/docs/api/java/lang/Long.html#compareUnsigned-long-long- - 否则，您正在失去位存储的时空效率，因为要来回转换以处理基于使用不为其设计的类的情况。 BitSet#xor()和（特别是）BitSet#length()都不是您从位运算中期望的轻量级操作，主要是由于其中使用了recalculateWordsInUse();，checkInvariants();和Long.numberOfLeadingZeros()。总之，在任何性能相关的场景中，除了本机整数使用（尤其是上面显示的任何比较代码），所有其他方法都会导致严重的性能损失。

- user719662

---

你可以使用 Long.compare()。 - fge

谢谢您的解释，为什么BitSet不是Comparable类型，以及将其转换为/从整数的方法确实非常优雅。 - Mangat Rai Modi

@dasblinkenlight，我已经注意到了，“请注意，在这种特殊情况下，两个集合都必须适合长整型（最多63位）。” - user719662

Answer 3

您可以使用逻辑运算符进行位运算（从get()中获取的布尔值）：

// Assumed equal length
boolean less(BitSet b1, BitSet b2) {
 int N = b1.length();

 for (int i = N-1; i >= 0; i--) {
    if (b1.get(i) ^ b2.get(i)) return b2.get(i);
 }

 return false;
}

或者您可以使用比较器：

class BitsComparator implements Comparator<BitSet> {
  @Override
  int compare (BitSet b1, BitSet b2) {
    if (b1.length() > b2.length())
       return 1;
    if (b1.length() == b2.length()) {
      int N = b1.length();
      for (int i = N-1; i >= 0; i--) {
        if ((b1.get(i) ^ b2.get(i)) && b2.get(i)) return -1;
      }
      return 0;
    }
    return -1;
  }
}

- nitishagar

---

谢谢您的回答。顺便说一句，您可能需要将x、y分别替换为b1、b2... - Mangat Rai Modi

好的，现在已经修复了。对此感到抱歉 :) - nitishagar