Btukfyl

I was reading Unsigned arithmetic in Java which nicely explained how to do unsigned longs using the following method

public static boolean isLessThanUnsigned(long n1, long n2) {

  return (n1 < n2) ^ ((n1 < 0) != (n2 < 0));

}

However I'm confused by Guava's implementation. I'm hoping someone can shed some light on it.

  /**

   * A (self-inverse) bijection which converts the ordering on unsigned longs to the ordering on

   * longs, that is, {@code a <= b} as unsigned longs if and only if {@code flip(a) <= flip(b)} as

   * signed longs.

   */

  private static long flip(long a) {

    return a ^ Long.MIN_VALUE;

  }



  /**

   * Compares the two specified {@code long} values, treating them as unsigned values between

   * {@code 0} and {@code 2^64 - 1} inclusive.

   *

   * @param a the first unsigned {@code long} to compare

   * @param b the second unsigned {@code long} to compare

   * @return a negative value if {@code a} is less than {@code b}; a positive value if {@code a} is

   *     greater than {@code b}; or zero if they are equal

   */

  public static int compare(long a, long b) {

    return Longs.compare(flip(a), flip(b));

  }

Perhaps some diagrams help. I'll use 8 bit numbers to keep the constants short, it generalizes to ints and longs in the obvious way.

Absolute view:

Unsigned number line:

                [ 0 .. 0x7F ][ 0x80 .. 0xFF]

Signed number line:

[ 0x80 .. 0xFF ][ 0 .. 0x7F]

Relative view:

Unsigned number line:

[ 0 .. 0x7F ][ 0x80 .. 0xFF]

Signed number line:

[ 0x80 .. 0xFF ][ 0 .. 0x7F]

So signed and unsigned numbers largely have the same relative order, except that the two ranges with the sign bit set and the sign bit not set are swapped in order. Inverting that bit of course swaps the order.

x ^ Long.MIN_VALUE inverts the sign bit for a long.

This trick is applicable for any operation that depends only on the relative order, for example comparisons and directly related operations such as min and max. It does not work for operations that depend on the absolute magnitude of the numbers, such as division.

Consider the bits that make up a long type. Performing ^ Long.MIN_VALUE converts a regular two's complement signed representation that holds [-2⁶³, 2^63-1] values into an unsigned representation that holds [0, 2^64-1] values.

You can see the process by taking the smallest long value, adding one and "flipping" while inspecting the bits (e.g. with Long.toBinaryString()):

• 
  Long.MIN_VALUE ^ Long.MIN_VALUE is 00..00 (all 64 bits unset)
  


• 
  (Long.MIN_VALUE + 1) ^ Long.MIN_VALUE is 00..01
  


• 
  (Long.MIN_VALUE + 2) ^ Long.MIN_VALUE is 00..10
  


• 
  (Long.MIN_VALUE + 3) ^ Long.MIN_VALUE is 00..11
  

and so on until:

• 
  Long.MAX_VALUE ^ Long.MIN_VALUE is 11..11 (all 64 bits set)
  

The "flip" is done because Longs.compare() needs input as unsigned [0, 2^64-1] values as per the method javadoc in your example:

/**

 * Compares the two specified {@code long} values, treating them as unsigned values between

 * {@code 0} and {@code 2^64 - 1} inclusive.

 *