Guava 的 UnsignedLong：为什么要异或 Long.MIN_VALUE

Question

我正在阅读 Unsigned arithmetic in Java，它很好地解释了如何使用以下方法进行无符号长整型

public static boolean isLessThanUnsigned(long n1, long n2) {
  return (n1 < n2) ^ ((n1 < 0) != (n2 < 0));
}

但是我对 Guava 的实现感到困惑。我希望有人能对此有所启发。

  /**
   * 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));
  }

Answer 1

考虑构成 long 类型的位。执行 ^ Long.MIN_VALUE 将包含 [-2⁶³, 2^63-1] 值的常规 two's complement 符号表示转换为包含 [0, 2^64-1] 值的无符号表示。

您可以通过取最小的 long 值，在检查位时添加 1 和 "flipping" 来查看过程（例如 Long.toBinaryString()）：

Long.MIN_VALUE ^ Long.MIN_VALUE 是 00..00 （所有 64 位未设置）
(Long.MIN_VALUE + 1) ^ Long.MIN_VALUE 是 00..01
(Long.MIN_VALUE + 2) ^ Long.MIN_VALUE 是 00..10
(Long.MIN_VALUE + 3) ^ Long.MIN_VALUE 是 00..11

依此类推，直到：

Long.MAX_VALUE ^ Long.MIN_VALUE 是 11..11 （所有 64 位设置）

"flip" 已完成，因为 Longs.compare() 需要根据示例中的方法 javadoc 输入无符号 [0, 2^64-1] 值:

/**
 * Compares the two specified {@code long} values, treating them as unsigned values between
 * {@code 0} and {@code 2^64 - 1} inclusive.
 *

Answer 2

也许一些图表有帮助。我将使用 8 位数字来保持常量简短，它以明显的方式推广到整数和长整数。

绝对视图：

Unsigned number line:
                [ 0 .. 0x7F ][ 0x80 .. 0xFF]
Signed number line:
[ 0x80 .. 0xFF ][ 0 .. 0x7F]

相对观点：

Unsigned number line:
[ 0 .. 0x7F ][ 0x80 .. 0xFF]
Signed number line:
[ 0x80 .. 0xFF ][ 0 .. 0x7F]

所以有符号数和无符号数在很大程度上具有相同的相对顺序，除了设置符号位和未设置符号位的两个范围按顺序交换。反转那个位当然会交换顺序。

x ^ Long.MIN_VALUE 反转 long.

的符号位

这个技巧适用于任何只依赖于相对顺序的操作，例如比较和直接相关的操作，如最小值和最大值。它不适用于依赖于数字绝对大小的运算，例如除法。

Guava 的 UnsignedLong：为什么要异或 Long.MIN_VALUE

Guava's UnsignedLong: Why does it XOR Long.MIN_VALUE

java

guava

long-integer