Aggiunta saturata di due valori "long" Java firmati

Question

In che modo è possibile aggiungere due valori long in Java in modo che se il risultato trabocca, viene bloccato sull'intervallo Long.MIN_VALUE .. Long.MAX_VALUE?

Per aggiungere interi si può eseguire l'aritmetica in long precisione e gettato il risultato di nuovo ad un int, ad esempio:

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

o

import com.google.common.primitives.Ints; 

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

ma nel caso di long non c'è più grande tipo primitivo che può contenere la somma intermedia (non chiusa).

Dal momento che questo è Java, non posso usare inline assembly (nelle istruzioni add saturi particolare del SSE.)

Può essere implementato usando BigInteger, per esempio

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

tuttavia le prestazioni sono importanti quindi questo metodo non è ideale (anche se utile per i test.)

Io non so se evitando ramificazione può influenzare in modo significativo le prestazioni in Java. Presumo che possa, ma mi piacerebbe confrontare i metodi con e senza branching.

correlati: How to do saturating addition in C?

Answer 1

si dovrebbe essere in grado di spezzare in quattro casi in base al segno dei numeri: Se uno dei numeri è zero, la risposta è l'altro numero. Se uno è positivo e un altro negativo, non è possibile eseguire un over o underflow. Se entrambi sono positivi, puoi solo traboccare. Se entrambi sono negativi, è possibile solo underflow.

Basta fare un calcolo in più per gli ultimi due casi, per vedere se il risultato sarà nel caso non desiderato:

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

Ecco il mio tentativo di una versione senza ramo:

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

È possono anche utilizzare il meccanismo di saturazione integrato di tipo-casting:

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

x e vengono aggiunti come double e la trasmissione a int si saturerà nell'intervallo [Integer.MIN_VALUE, Integer.MAX_VALUE].

Questo non è adatto per long s come la precisione di double è inferiore a quello di long, ma se la precisione non è così importante, sarà sufficiente.