Ajout saturé de deux valeurs Java «longues» signées

Question

Comment ajouter deux valeurs long en Java de sorte que si le résultat déborde, il est bloqué à la plage Long.MIN_VALUE .. Long.MAX_VALUE?

Pour ajouter ints, on peut effectuer l'arithmétique dans long précision et jeter le résultat à un int, par exemple:

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

ou

import com.google.common.primitives.Ints; 

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

mais dans le cas de long il n'y a type primitif plus grand qui peut contenir la somme intermédiaire (débloqué).

Depuis c'est Java, je ne peux pas utiliser inline assembly (en particulier de l'ESS instructions d'add saturés.)

Il peut être mis en œuvre à l'aide BigInteger, par exemple

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

cependant la performance est importante pour cette méthode est idéale (si utile pour les tests.)

Je ne sais pas si d'éviter peut ramification affecter de manière significative les performances en Java. Je suppose qu'il peut, mais je voudrais comparer les méthodes avec et sans branchement.

connexes: How to do saturating addition in C?

Answer 1

Vous devriez être en mesure de le casser en quatre cas, en fonction du signe des chiffres: Si l'un des numéros est égal à zéro, la réponse est l'autre numéro. Si l'un est positif et l'autre négatif, vous ne pouvez pas dépasser ou déborder. Si les deux sont positifs, vous ne pouvez que déborder. Si les deux sont négatifs, vous ne pouvez que déborder.

Il suffit de faire un calcul supplémentaire pour les deux derniers cas pour voir si cela se traduira dans le cas indésirable:

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

Voici ma tentative d'une version sans branche:

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

Vous peut également utiliser le mécanisme de saturation intégré du type à coulée:

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

x et y sont ajoutés en tant que double et la conversion en int saturera à la plage [Integer.MIN_VALUE, Integer.MAX_VALUE].

Ce n'est pas aussi approprié pour long s que la précision de double est inférieure à celle de long, mais si la précision n'est pas aussi importante, cela suffira.