Java: BitSet comparison

Question

Suppose we have two BitSet objects in Java with values as

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

How can we compare B1 and B2 to know that the value represented by B1 is greater than that by B2.

are logical operators (>,<,==) overloaded for BitSet? or Do I have to write my own implementation?

Update: just found that "The operator > is undefined for the argument type(s) java.util.BitSet, java.util.BitSet". Is there any built-in way to do so?

Answer 1

You can do it by xor-ing the two sets together, and comparing the length of the result to lengths of bit sets:

• If xor is empty, bit sets are equal. You can bypass this operation by calling equals()
• Otherwise, the length of xor result will be equal to the position of the most significant bit that is different between the two values.
• Whichever of the two operands has this bit set is the greater one of the two.

Here is a sample implementation:

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

Demo.

Answer 2

No, the operators aren't overloaded, because a) there is no operator overloading in Java, b) what you expect is kind of wrong and illogical.

BitSet is, like the name signifies a set of bits. You can't tell a "greater" and "smaller" set - it's like saying one color is "bigger" than the other. If you want to compare bit sets, you have to create a comparison metric - I think what you want is to compare values of the integers created from bits - if that's the case, use the code from e.g. BitSet to and from integer/long, and then call

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

or, as a Comparator,

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

Note that in this particular case both sets have to fit into long (63 bits max). Alternatively, assuming your metric is "the set with higher unsigned integer representation is bigger", you can use XORing, or loop through the bits, or any other construct that goes through all the bits -

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

but in all of those cases, if you're aiming at comparing your bits, your best bet is just to use long to store your data and then compare it directly as unsigned values, using https://docs.oracle.com/javase/8/docs/api/java/lang/Long.html#compareUnsigned-long-long- - otherwise you're losing the space-time efficiency of bit storage with doing to-and-fro conversions to deal with a case that's based on using a class for things it's not designed for. Both BitSet#xor() & (especially) BitSet#length() aren't the light-weight operations you'd expect from bit ops, mainly due to recalculateWordsInUse();, checkInvariants(); & Long.numberOfLeadingZeros() used in them. All in all, all methods other than native integer use (especially any comparing code as shown above) will result in serious performance loss in any performance-dependent scenarios.

Answer 3

You can use the logical operator on bit basis (boolean values received from 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;
}

Or you can have a comparator in place:

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