Насыщенное сложение двух длинных значений Java со знаком - PullRequest
Новая
       38

Насыщенное сложение двух длинных значений Java со знаком

9 голосов
/ 13 апреля 2010

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

Для добавления целых чисел можно выполнить арифметику с точностью 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?

Ответы [ 4 ]

5 голосов
/ 13 апреля 2010

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

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

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;
}
2 голосов
/ 14 июля 2014

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

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

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

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

2 голосов
/ 14 апреля 2010

Вот моя попытка версии без ветки: 

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;
}
0 голосов
/ 10 апреля 2018

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

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;
    }

Кроме того, мы могли бы принудительно сложить два if, написав (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. Это не улучшает читаемость, но выглядит «круто» и более симметрично: 

    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;
...