Gesättigte Addition von zwei signierten Java-Long-Werten

Question

Wie kann man zwei long Werte in Java hinzufügen, so dass, wenn das Ergebnis überläuft, es in den Bereich Long.MIN_VALUE .. Long.MAX_VALUE geklemmt wird?

Für ints Zugabe kann man die arithmetische in long Präzision durchzuführen und das Ergebnis zurück in ein int gegossen, zum Beispiel:

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

oder

import com.google.common.primitives.Ints; 

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

aber im Fall von long es keine größerer primitiver Typ, der die Zwischensumme (nicht geklammerte Summe) enthalten kann.

Da es sich um Java, kann ich nicht inline assembly verwenden (insbesondere gesättigte des SSE Add Anweisungen.)

Es implementiert werden kann BigInteger, z.B.

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

aber Leistung ist wichtig, so dass diese Methode nicht ideal ist (wenn auch nützlich für die Prüfung.)

Ich weiß nicht, ob Verzweigung vermieden die Leistung erheblich in Java beeinflussen kann. Ich nehme an, dass es möglich ist, aber ich möchte Methoden mit und ohne Verzweigung benchmarken.

Verwandte: How to do saturating addition in C?

Answer 1

sollten Sie in der Lage sein, es in vier Fällen zu brechen, basierend auf dem Vorzeichen der Zahlen: Wenn eine der Zahlen Null ist, die Antwort ist die andere Zahl. Wenn einer positiv und ein anderer negativ ist, dann können Sie nicht über- oder unterlaufen. Wenn beide positiv sind, können Sie nur überlaufen. Wenn beide negativ sind, können Sie nur unterlaufen.

tun nur eine zusätzliche Berechnung für die letzten beiden Fälle zu sehen, ob es in dem unerwünschten Fall führen:

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

Hier ist mein Versuch einer astfreien Version:

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

Sie können auch die integrierten Sättigungsmechanismus des Typs Gießen verwendet werden:

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

x und y werden als double hinzugefügt, und Gießen auf int wird in den Bereich [Integer.MIN_VALUE, Integer.MAX_VALUE] gesättigt.

Dies ist nicht so geeignet für long s als Präzision von double ist weniger als das von long, aber wenn die Genauigkeit nicht so wichtig ist, wird es ausreichen.