Беззнаковая арифметика в Java

Как известно, в Java нет беззнаковых типов. Если в Си вы могли написать unsigned int (char, long), то в Java так не получится. Однако нередко возникает необходимость в выполнении арифметических операций именно с числами без знака. На первый взгляд кажется, что беззнаковые типы в принципе-то и не особо нужны (подумаешь, MaxInt для чисел со знаком меньше в два раза, если нужны числа больше, я просто возьму long и далее BigInteger). Но основное различие на самом деле не в том, сколько различных неотрицательных чисел можно положить в signed или unsigned int, а в том, как над ними производятся арифметические операции и сравнения. Если вы работаете с бинарными протоколами или с двоичной арифметикой, где важен каждый используемый бит, нужно уметь выполнять все основные операции в беззнаковом режиме. Рассмотрим эти операции по порядку:

Преобразование byte в short (int, long)

Обычный каст (int) myByte выполнит расширение до 32 бит со знаком — это означает, что если старший бит байта был установлен в 1, то результатом будет то же самое отрицательное число, но записанное в 32-битном формате:

0xff -> 0xffffffff (-1)

Часто это не то, чего бы мы хотели. Для того, чтобы выполнить расширение до 32 бит без знака и получить 0x000000ff, в Java можно записать:

int myInt = myByte & 0xff;
short myShort = myByte & 0xff;

Сравнение без учёта знака

Для беззнакового сравнения есть лаконичная формула:

int compareUnsigned(int a, int b) {
    return Integer.compare( a ^ 0x80000000, b ^ 0x80000000 );
}

Для byte, short и long, соответственно, константы будут 0x80, 0x8000 и 0x8000000000000000L.

Сложение, вычитание и умножение

А вот здесь приятный сюрприз — эти операции выполняются корректно в любом случае. Но в выражениях необходимо тщательно следить за тем, чтобы операции выполнялись с числами одного типа, так как любые неявные преобразования выполняются с расширением знака, и могут приводить к результатам, отличным от ожидаемых. Коварство таких багов в том, что ошибочный сценарий может выполняться очень редко.

Деление

Деление -256 на 256 даст нам -1. А нам бы хотелось, чтобы 0xffffff00 / 0x100 давало 0x00ffffff, а не 0xffffffff (-1). Для byte, short и int решением будет переход к числам большей разрядности:

int a = 0xffffff00;
int b = 0x100;
int c = (int) ((a & 0xffffffffL) / b); // convert a to long before division

Но что делать с long? Переходить на BigInteger в таких случаях обычно не вариант — слишком медленно. Остаётся только брать всё в свои руки и реализовывать деление вручную. К счастью, всё уже украдено до нас — в Google Guava есть реализация беззнакового деления для long, причём довольно шустрая. Если вы не используете эту библиотеку, проще всего выдрать кусок кода прямо из файла UnsignedLongs.java:

  /**
   * Returns dividend / divisor, where the dividend and divisor are treated as unsigned 64-bit
   * quantities.
   *
   * @param dividend the dividend (numerator)
   * @param divisor the divisor (denominator)
   * @throws ArithmeticException if divisor is 0
   */
  public static long divide(long dividend, long divisor) {
    if (divisor < 0) { // i.e., divisor >= 2^63:
      if (compare(dividend, divisor) < 0) {
        return 0; // dividend < divisor
      } else {
        return 1; // dividend >= divisor
      }
    }

    // Optimization - use signed division if dividend < 2^63
    if (dividend >= 0) {
      return dividend / divisor;
    }

    /*
     * Otherwise, approximate the quotient, check, and correct if necessary. Our approximation is
     * guaranteed to be either exact or one less than the correct value. This follows from fact
     * that floor(floor(x)/i) == floor(x/i) for any real x and integer i != 0. The proof is not
     * quite trivial.
     */
    long quotient = ((dividend >>> 1) / divisor) << 1;
    long rem = dividend - quotient * divisor;
    return quotient + (compare(rem, divisor) >= 0 ? 1 : 0);
  }

Чтобы код компилировался, придётся также позаимствовать реализацию compare(long, long):

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

и Longs.compare(long, long) + flip(long):

  /**
   * 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. The sign of the value
   * returned is the same as that of {@code ((Long) a).compareTo(b)}.
   *
   * @param a the first {@code long} to compare
   * @param b the second {@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 (a < b) ? -1 : ((a > b) ? 1 : 0);
  }

Побитовые сдвиги

Чтобы окончательно покрыть тему о битовых операциях, вспомним также о сдвигах. В x86 ассемблере есть целая пачка различных команд, которые делают побитовые сдвиги — SHL, SHR, SAL, SAR, ROR, ROL, RCR, RCL. Последние 4 осуществляют циклические сдвиги, их эквивалентов в Java нет. А вот логические и арифметические сдвиги присутствуют. Логический сдвиг (не учитывает знака) — SHL (shift left) и SHR (shift right) — реализуется в Java операторами << и >>> соответственно. С помощью логических сдвигов можно быстро выполнять целочисленные умножение и деление на числа степени двойки. Арифметический сдвиг (учитывает знак) вправо — SAR — реализуется оператором >>. Арифметический сдвиг влево эквивалентен логическому, и поэтому специального оператора для него нет. Может показаться странным, что в ассемблере есть специальный опкод для этой операции, но на самом деле он делает то же самое, то есть SAL полностью повторяет поведение SHL, и об этом прямо говорит документация от Intel:

The shift arithmetic left (SAL) and shift logical left (SHL) instructions perform the same operation; they shift the bits in the destination operand to the left (toward more significant bit locations). For each shift count, the most significant bit of the destination operand is shifted into the CF flag, and the least significant bit is cleared (see Figure 7-7 in the Intel®64 and IA-32 Architectures Software Developer'sManual, Volume 1).

То есть SAL добавили просто для симметрии, с учётом того, что для сдвига вправо есть разделение на логический и арифметический. Ну а Гослинг решил не заморачиваться (и, думается, правильно сделал).

Итак, мы имеем следующее:

a << 1; // беззнаковый сдвиг влево, эквивалентно умножению на 2
a >> 1; // сдвиг вправо с учётом знака (эквивалентно делению на 2)
a >>> 1; // сдвиг вправо без учёта знака (эквивалентно беззнаковому делению на 2)

Заключительные рекомендации

• При выполнении арифметических действий, которые могут привести к переполнению в выбранной разрядной сетке, нужно всегда точно представлять, какая область допустимых значений может быть у переменных, и отслеживать эти инварианты, расставляя утверждения (assertions). Например, очевидно, что при умножении двух произвольных 32-разрядных беззнаковых чисел результат может не поместиться в 32 бита, и если вам нужно избежать переполнения, нужно либо убедиться, что в этом месте никогда не будет ситуации, при которой произведение не влезает в 32 бита, либо необходимо предварительно сконвертировать оба операнда в long (выполнив a & 0xffffffffL). Здесь, кстати, можно легко допустить ошибку, сконвертировав только один из операндов. Нет, нужно сконвертировать в long оба, т.к. если второй операнд окажется отрицательным, он будет неявно преобразован в long с расширением знака, и результат умножения будет неправильным.
• Щедро расставляйте скобки в выражениях, где используются побитовые операции. Дело в том, что приоритет побитовых операторов в Java несколько странный, и часто ведёт себя неочевидным образом. Лучше добавить пару скобок, чем потом несколько часов искать трудноуловимые ошибки.
• Если вам нужна константа типа long, не забудьте добавить суффикс L в конец литерала константы. Если этого не сделать, это будет не long, а int, и при неявном приведении к long снова произойдёт неприятное нам расширение со знаком.

Автор: elw00d

Источник