Saturated addition of two signed Java 'long' values

Question

How can one add two long values in Java so that if the result overflows then it is clamped to the range Long.MIN_VALUE..Long.MAX_VALUE?

For adding ints one can perform the arithmetic in long precision and cast the result back to an int, e.g.:

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

or

import com.google.common.primitives.Ints;

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

but in the case of long there is no larger primitive type that can hold the intermediate (unclamped) sum.

Since this is Java, I cannot use inline assembly (in particular SSE's saturated add instructions.)

It can be implemented using BigInteger, e.g.

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

however performance is important so this method is not ideal (though useful for testing.)

I don't know whether avoiding branching can significantly affect performance in Java. I assume it can, but I would like to benchmark methods both with and without branching.

Related: http://stackoverflow.com/questions/121240/saturating-addition-in-c

Answer 1

You should be able to to break it into four cases based on the sign of the numbers: If one of the numbers is zero, the answer is the other number. If one is positive and another negative, then you can't over or underflow. If both are positive you can only overflow. If both are negative you can only underflow.

Just do an extra calculation for the last two cases to see if it will result in the undesired case:

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

Here's my attempt at a branch-free 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;
}