Беззнаковая арифметика в 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 снова произойдёт неприятное нам расширение со знаком.
    Share post

    Similar posts

    Comments 27

      –1
      & 0xff
        +3
        И еще, много где встречал использование char как uint16
          +1
          Для беззнакового short во многих ситуациях можно также использовать char.
            +2
            Почему не упоминаете Integer(Long).compare(divide)Unsigned() методы?

            Последние 4 осуществляют циклические сдвиги, их эквивалентов в Java нет.

            А как же Integer.rotateLeft(Right)?
              0
              Оп-па, а я и забыл про rotateLeft-Right. Спасибо. А про Integer(Long).compare(divide)Unsigned() не понял — в стандартной библиотеке вроде бы такого нет.
                0
                В Java 8, которая уже, на минуточку, скоро полгода как основная версия.
                  +4
                  У кого-то она, может, и основная, но самая распространённая Java-платформа недавно только на Java7 (и то не полностью) переползла.
                    0
                    Это здорово, что в 8 появились! А я смотрел в доках к семёрке, поэтому и не увидел. Но всё равно пока придётся уж иметь в виду ручные реализации деления и сравнения, поддержка семёрки всё-таки желательная вещь сейчас.
                  +2
                  Посмотрите реализацию Long.divideUnsigned, он считает в BigInteger'ах если делитель отрицателен :(
                  +1
                  Что-то туплю, в чём смысл «Integer.compare( a ^ 0x80000000, b ^ 0x80000000 );»?
                  Ведь мы меняем знак (старший бит) у обоих операндов, нет?
                    0
                    Эта операция (инвертирование знака) проецирует пространство значений [0;2^32-1] на [-2^31;2^31-1] для обоих операндов. Далее производится обычное сравнение. Например, было число -1 (0xffffffff), оно станет 0x7fffffff. Было число 10 (0x0000000a), станет -10 (0x8000000a). 0x7fffffff > 0x8000000a.
                      +5
                      На самом деле это такая небольшая обфускация: правильнее будет Integer.compare(a - 0x80000000, b - 0x80000000);, где как бы понятно как всё работает. Мы переходим от чисел в интервале от 0 до 0xffffffff к часлам в интервале от 0x80000000 до 0x7ffffff путём линейного сдвига (мы стартуем с чисел без знака, а результатом является число без знака, но «так можно», потому что в арифметике «с дополнением до двух» сложение и вычитанием одинаково и для чисел без знака и для чисел со знаком) — а после этого уже все сравнения нормально можно производить.

                      Подобные же трюки часто приходится производить работая с SSE.

                      Ну а дальше можно заметить что 0x80000000 — это такое особенное число, что его что вычесть, что прибавить, что про XOR'ить — всё равно. Не знаю, правда, какой смысл в этой обфускации.
                        0
                        Не знаю, правда, какой смысл в этой обфускации.

                        Побитовые операции быстрее (хотя на дворе 2014 год, и может уже и не быстрее).
                          0
                          Сколько же вам лет-то? Побитовые операции были быстрее в компьютерах 70х годов (и то не во всех)! Уже в 80е сложение выполнялось с такой же скоростью как и побитовые операции!
                          +2
                          Собственно, в 8 джаве так и сделано
                          public static int compareUnsigned(int x, int y) {
                                  return compare(x + MIN_VALUE, y + MIN_VALUE);
                          }
                          
                        –3
                        И зачем так сложно long делить.
                        Что плохо в этом:
                            public static long ulongDiv(final long a, final long b) {
                        		return b>1L || b<0 ? (a>>>1)/(b>>>1) : a/b;
                        	}

                        Одна строчка — всё инлайнится и оптимизируется.
                          +2
                          А теперь представьте, что через 3 года натыкаетесь на этот кусок кода. Сколько вам понадобиться времени, чтобы понять как это работает?
                            +2
                            Если я его за пять секунд придумал, то очевидно, что пять секунд. А во-вторых, вся подобная магия должна быть документирована. Тут даже по имени функции видно, что она делает.
                            Это не более запутано чем Integer.compare( a ^ 0x80000000, b ^ 0x80000000 ) и уж точно гораздо более понятно, чем тот, кусок кода из пяти функций, который в статье приведен. Вы внимательно посмотрели, что именно в статье предлагается использовать? Четыре процедуры, два из которых весьма не очевидны. А уж оптимизация сравнивать…
                              +1
                              И да, кстати, вы что не видите, что я просто беззнаково сокращаю делитель и делимое на два, выводя их в диапазон положительных чисел? По-моему, это заметно пятой секунде. Из которых четыре уходит на то, чтобы понять, что условие нужно для случая, когда делитель меньше двойки и сокращать нельзя.
                            +9
                            ulongDiv(10, 3) возвращает 5
                              0
                              Косячок-с :) Нужно ещё одно условие ввести. :)
                                0
                                На самом деле нужно доказывать корректность для всего множества значений :-)
                                И желательно приложить сокращенный вариант доказательства прямо в JavaDoc.
                            –3
                            Собственно, даже проще:
                            public static long ulongDiv(final long a, final long b) {
                            return b!=1L? (a>>>1)/(b>>>1): a/b;
                            }
                            В отличи от гугеля, понятно, инлайнится и скорее всего для констант будет просто статически вычислено. Причём, если b — константа, то тоже будет отлично заоптимизированно.
                              +23
                              Да вы прямо математик, да. Делим 9 на 3 и получаем… 4. Это ж просто праздник какой-то!

                              P.S. Только не надо приводить ещё один «ещё более очевидный» вариант. В конце-концов доберётесь-таки до чего-то подобного Гугловому варианту. С 10й попытки. Я в вас верю. Но вопрос «почему всем идиотам всё далеко не так очевидно, как мне» вроде как уже отпал. Или нет?
                              +1
                              Я бы еще добавил самой первой рекомендацией: Никогда не используйте нигде, кроме тщательно локализованных модулей взаимодействия с legacy данными и низкоуровневыми протоколами.
                              В библиотеке javolution есть класс Struct для работы с такого типа данными.
                                +4
                                Для каких-то исключительных случаев такой метод, возможно, и будет полезным, но я в java скорее предпочту использовать знаковые типы достаточной для хранения данных разрядности, нежели городить подобные обёртки. Просто потому, что в процессе разработки все эти пляски забудутся, и начнутся чудеса при сравнении знаковых с беззнаковыми, «неправильными» операциями и т.д.
                                  0
                                  Если такая магия и нужна, то ее лучше обернуть классом, и использовать как объект-значение.
                                  Жаль, что в Java (как и в большинстве языков) нельзя создавать производных типов над примитивными.

                                Only users with full accounts can post comments. Log in, please.