Влажное добавление двух подписанных Java 'долго' оценивает
Как можно добавить два long значения в Java так, чтобы, если результат переполняет затем его, был зафиксирован к диапазону Long.MIN_VALUE..Long.MAX_VALUE?
Для добавления ints можно выполнить арифметику в long точность и бросок результат назад к int, например:
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;
}
или
import com.google.common.primitives.Ints;
int saturatedAdd(int x, int y) {
long sum = (long) x + (long) y;
return Ints.saturatedCast(sum);
}
но в случае long нет никакого большего типа примитива, который может содержать (разблокированную) сумму промежуточного звена.
Так как это - Java, я не могу использовать встроенный ассемблерный код (в особенности, SSE насыщал, добавляют инструкции.)
Это может быть реализовано с помощью BigInteger, например.
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();
}
однако производительность важна, таким образом, этот метод не идеален (хотя полезный для тестирования.)
Я не знаю, может ли предотвращение ветвления значительно влиять на производительность в Java. Я предполагаю, что это может, но я хотел бы к методам сопоставления и с и без ветвления.
Похожие страницы: Как сделать дополнение насыщения в C?
2 ответа
Вы можете разбить это число на четыре случая в зависимости от знака чисел: Если одно из чисел равно нулю, ответ будет другим числом. Если один - положительный и другой отрицательный, тогда вы не можете переполнить или опустошить. Если оба положительные, вы можете только переполнить. Если оба отрицательные, вы можете только переполнить.
Просто сделайте дополнительный расчет для последних двух случаев, чтобы увидеть, приведет ли это к нежелательному случаю:
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;
}
Вот моя попытка создать версию без веток:
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;
}