Насыщенное добавление двух подписанных значений Java

Question

Как можно добавить два long значения в Java так, что если результат переполняется, то он зажимается в диапазоне Long.MIN_VALUE..Long.MAX_VALUE?

Для добавления ints можно выполнить арифметику в long точность и отбрасывать результат назад к int, например:

int saturatedAdd(int x, int y) {
  long sum = (long) x + (long) y;
  long clampedSum = Math.max((long) Integer.MIN_VALUE,
                             Math.min(sum, (long) Integer.MAX_VALUE));
  return (int) clampedSum;
}

или

import com.google.common.primitives.Ints;

int saturatedAdd(int x, int y) {
  long sum = (long) x + (long) y;
  return Ints.saturatedCast(sum);
}

но в случае long Нет большего примитивного типа, который может удерживать промежуточную (ненужденную) сумму.

Так как это Java, я не могу использовать встроенный сборник (В частности, насыщенные насыщенные инструкции SSE.)

Это может быть реализовано с использованием BigInteger, например,

static final BigInteger bigMin = BigInteger.valueOf(Long.MIN_VALUE);
static final BigInteger bigMax = BigInteger.valueOf(Long.MAX_VALUE);

long saturatedAdd(long x, long y) {
    BigInteger sum = BigInteger.valueOf(x).add(BigInteger.valueOf(y));
    return bigMin.max(sum).min(bigMax).longValue();
}

Однако производительность важно, поэтому этот метод не идеален (хотя и полезен для тестирования.)

Я не знаю, следует ли избежать ветвления значительно повлиять на производительность в Java. Я предполагаю, что это может, но я хотел бы ориентировать методы как с ветвями и без ветвления.

Связанный: Как сделать насыщение дополнения в C?

Answer 1

Вы должны быть в состоянии сломать его на четыре случая, основанные на знаке чисел: если один из чисел равен нулю, ответ - это другой номер. Если кто-то положительный и другой отрицательный, то вы не можете закончиться или недовольны. Если оба позитивны, вы можете только переполнить. Если оба негативы, вы можете только поднять.

Просто сделайте дополнительный расчет за последние два случая, чтобы увидеть, приведет ли он в нежелательном случае:

if(x == 0 || y == 0 || (x > 0 ^ y > 0)){
  //zero+N or one pos, another neg = no problems
  return x+y;
}else if(x > 0){
  //both pos, can only overflow
  return Long.MAX_VALUE - x < y ? Long.MAX_VALUE : x+y;
}else{
  //both neg, can only underflow
  return Long.MIN_VALUE - x > y ? Long.MIN_VALUE : x+y;
}

Answer 2

Вот моя попытка бесплатной отделкой версии:

long saturatedAdd(long x, long y) {
    // Sum ignoring overflow/underflow
    long s = x + y;

    // Long.MIN_VALUE if result positive (potential underflow)
    // Long.MAX_VALUE if result negative (potential overflow)
    long limit = Long.MIN_VALUE ^ (s >> 63);

    // -1 if overflow/underflow occurred, 0 otherwise
    long overflow = ((x ^ s) & ~(x ^ y)) >> 63;

    // limit if overflowed/underflowed, else s
    return ((limit ^ s) & overflow) ^ s;
}

Answer 3

Вы также можете использовать встроенный механизм насыщения типа литья типа:

int saturatedAdd(int x, int y) {
    return (int)(x + (double) y);
}

x и y добавляются как double, и лить int будет насыщать [Integer.MIN_VALUE, Integer.MAX_VALUE] диапазон.

Это не так подходит для longS как точность double меньше, чем у long, но если точность не так важно, это будет достаточно.

Answer 4

Давайте начнем с простой формы с комментариями:

long saturatedAdd(long x, long y) {
    long r = x + y;

    // Addition is safe from overflow if x and y have different signs
    if ((x < 0) != (y < 0)) {
        return r;
    }

    // Result has overflowed if the resulting sign is different
    if ((r < 0) != (x < 0)) {
        return x < 0 ? Long.MIN_VALUE : Long.MAX_VALUE;
    }

    // Otherwise result has not overflowed
    return r;
}

Хотя нет ничего плохого в использовании этой реализации, в дальнейшем является попытка микро- «оптимизировать» только ради аргумента.

То (x < 0) != (y < 0) можно изменить на (x ^ y) < 0 что по существу побито XOR знака бита.

    // Addition safe from overflow if x and y have different signs
    if ((x ^ y) < 0) {
        return r;
    }

    // Result has overflowed if resulting sign is different
    if ((r ^ x) < 0) {
        return x < 0 ? Long.MIN_VALUE : Long.MAX_VALUE;
    }

Кроме того, мы могли бы насильственно поставить два ifS вместе написав (x ^ y) < 0 || (r ^ x) >= 0 или даже ((x ^ y) | ~(r ^ x)) < 0. Отказ На данный момент он перестает быть читаемым:

    if (((x ^ y) | ~(r ^ x)) < 0) {
        return r;
    }
    return x < 0 ? Long.MIN_VALUE : Long.MAX_VALUE;

Мы могли бы взять намек на Math.exactAdd() и повернуть это if в ((r ^ x) & (r ^ y)) < 0. Отказ Это не улучшает читаемость, но выглядит «Cool» и более симметрично:

    if (((r ^ x) & (r ^ y)) < 0) {
        return x < 0 ? Long.MIN_VALUE : Long.MAX_VALUE;
    }
    return r;

Вот, это немного прыжка. По сути, это проверяет, Результат имеет другой знак для обоих входов, что возможно только если Оба входа имеют одинаковый знак И Полученный знак отличается от этого.

Двигаться вперед, добавление 1 к Long.MAX_VALUE приводит к Long.MIN_VALUE:

    if (((r ^ x) & (r ^ y)) < 0) {
        return Long.MAX_VALUE + (x < 0 ? 1 : 0);
    }
    return r;

Другой способ вывести один, когда x < 0 это использовать подписать бит как один.

    if (((r ^ x) & (r ^ y)) < 0) {
        return Long.MAX_VALUE + (x >>> (Long.SIZE - 1));
    }

Наконец, только ради симметрии, перейдите на использование r в этом битовой смене вместо x, давая нам:

    long r = x + y;
    if (((r ^ x) & (r ^ y)) < 0) {
        return Long.MIN_VALUE - (r >>> (Long.SIZE - 1));
    }
    return r;