Guava's UnsignedLong: почему он XOR Long.MIN_VALUE - PullRequest
Новая
       24

Guava's UnsignedLong: почему он XOR Long.MIN_VALUE

0 голосов
/ 23 ноября 2018

Я читал Арифметику без знака в Java , которая хорошо объясняла, как делать беззнаковые длинны, используя следующий метод 

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

Однако я запутался в реализации Гуавы.Я надеюсь, что кто-то может пролить свет на это. 

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

Ответы [ 2 ]

0 голосов
/ 23 ноября 2018

Возможно, некоторые диаграммы помогут.Я буду использовать 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.

Этот трюк применим для любой операции, которая зависит только от относительного порядка, дляпример сравнения и непосредственно связанные операции, такие как мин и макс.Он не работает для операций, которые зависят от абсолютной величины чисел, таких как деление.

0 голосов
/ 23 ноября 2018

Рассмотрим биты, которые составляют тип long.Выполнение ^ Long.MIN_VALUE преобразует обычное дополнение до двух знаковое представление, которое содержит значения [-2 63 , 2 63-1 ], в представление без знака, которое содержит [0, 2 64-1 ] значения.

Вы можете увидеть процесс, взяв наименьшее значение long, добавив единицу и «переворачивая» при проверке битов (например, с помощью 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 бита)

"Отразить" сделано, потому что Longs.compare() требует ввода в виде значений без знака [0, 2 64-1 ] согласно методу javadoc в вашем примере:

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