Java: BitSet比较

Question

假设在Java中有两个BitSet对象，其值为

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

如何比较B1和B2，才能知道B1所表示的值大于B2所表示的值。

逻辑运算符(>，<，==)是否过载于BitSet？还是我必须编写自己的实现？

Update:刚刚发现“操作符>对于参数类型java.util.BitSet，java.util.BitSet没有定义”。是否有任何内置的方式来做到这一点？

Answer 1

您可以通过xor-ing将这两个集合放在一起，并将结果的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;
}

演示。

Answer 2

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

BitSet和名称一样，表示一组位。你不能区分“大”和“小”的设置--这就像说一种颜色比另一种颜色“大”一样。如果您想比较位集，您必须创建一个比较度量--我认为您想要的是比较从位创建的整数的值--如果是这样的话，使用来自例如往返整数/长的BitSet的代码，然后调用

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位)。或者，假设您的度量是“具有较高无符号整数表示的集合更大”，则可以使用XORing，或循环遍历比特，或遍历所有位的任何其他构造-

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()。总之，除本机整数使用之外的所有方法(特别是上面所示的任何比较代码)在任何依赖性能的场景中都将导致严重的性能损失。

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;
  }
}