Nasycone dodanie dwóch podpisanych wartości Javy "długich"

Question

W jaki sposób można dodać dwie wartości long w Javie, aby w razie przepełnienia wynik był zaciśnięty do zakresu Long.MIN_VALUE .. Long.MAX_VALUE?

Aby dodać ints można wykonywać operacje arytmetyczne w long precyzją i oddanych wynik z powrotem do int, np:

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

lub

import com.google.common.primitives.Ints; 

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

ale w przypadku long tam nie ma większy prymitywny typ, który może pomieścić pośrednią sumę (bez zamków).

Ponieważ jest to Java, nie mogę używać inline assembly (nasyconych instrukcji SSE jest w szczególny sposób.)

To może być realizowane za pomocą BigInteger, np

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

jednak wydajność jest ważne, więc ta metoda nie jest idealna (choć przydatny do testowania.)

Nie wiem, czy unikanie rozgałęzień może znacząco wpłynąć na wydajność w Javie. Zakładam, że tak, ale chciałbym porównać metody zarówno z rozgałęzieniami, jak i bez nich.

pokrewne: How to do saturating addition in C?

Answer 1

powinien być w stanie złamać go w czterech przypadkach na podstawie znaku liczb: Jeśli jedna z liczb jest równa zero, to odpowiedź jest inna liczba. Jeśli jeden jest dodatni, a inny ujemny, to nie można go przekroczyć ani przekroczyć. Jeśli oba są dodatnie, możesz tylko przelać. Jeśli oba są ujemne, możesz tylko niedomiar.

Wystarczy zrobić dodatkowe obliczenia dla dwóch ostatnich przypadkach, aby sprawdzić, czy spowoduje to niepożądany przypadku:

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

Oto moja próba wersji oddziału bezpłatny:

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

Ty można również skorzystać z wbudowanego mechanizmu nasycenia typu rzucania:

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

x i y są dodawane jako double, a rzutowanie na int zostanie nasycone do zakresu [Integer.MIN_VALUE, Integer.MAX_VALUE].

Nie jest to odpowiednie dla long s ponieważ precyzja double jest mniejsza niż dokładność long, ale jeśli dokładność nie jest tak ważna, wystarczy.