Adición saturada de dos valores 'largos' de Java firmados

Question

¿Cómo se pueden agregar dos valores de long en Java para que, si el resultado se desborda, se fije en el rango Long.MIN_VALUE .. Long.MAX_VALUE?

Para añadir ints uno puede realizar la aritmética en long precisión y emitir el resultado de nuevo a un int, por ejemplo:

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

pero en el caso de long no hay tipo primitivo más grande que puede contener la suma intermedia (no bloqueada).

Dado que este es Java, no puedo usar inline assembly (en las instrucciones add saturados en particular de SSE.)

Se puede implementar usando BigInteger, por ejemplo

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

sin embargo el rendimiento es importante por lo que este método no es ideal (aunque útiles para la prueba.)

No sé si se puede evitar la ramificación afectar significativamente al rendimiento en Java. Supongo que sí, pero me gustaría comparar los métodos con y sin ramificación.

relacionadas: How to do saturating addition in C?

Answer 1

Usted debe ser capaz de romperlo en cuatro casos basados ​​en el signo de los números: Si uno de los números es cero, la respuesta es el otro número. Si uno es positivo y otro negativo, entonces no puede sobre o subdesbordamiento. Si ambos son positivos, solo puede desbordarse. Si ambos son negativos, solo puede desbordarse.

Sólo hacer un cálculo adicional para los dos últimos casos para ver si va a resultar en el caso no deseado:

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

Aquí está mi intento de una versión libre de la rama:

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

Usted también se puede utilizar el mecanismo de saturación incorporada del tipo de fundición:

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

x y y se agregan como double, y la conversión a int se saturará al rango [Integer.MIN_VALUE, Integer.MAX_VALUE].

Esto no es tan adecuado para long s como precisión de double es menor que la de long, pero si la precisión no es tan importante, será suficiente.