两个有符号 Java“长”的饱和加法价值观

Question

如何在 Java 中添加两个 long 值，以便在结果溢出时将其限制在 Long.MIN_VALUE..Long.MAX_VALUE 范围内>？

对于添加整数，可以以 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;
}

or

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 中进行饱和加法？

Answer 1

您应该能够根据数字的符号将其分为四种情况：
如果其中一个数字为零，则答案是另一个数字。
如果一个为正，另一个为负，那么就不能溢出或下溢。
如果两者都是正数，则只能溢出。
如果两者都是负数，则只能下溢。

只需对最后两种情况进行额外的计算，看看是否会导致不需要的情况：

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

这是我对无分支版本的尝试：

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

您还可以使用类型转换的内置饱和机制：

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

将x和y添加为double，并转换为int 将饱和到 [Integer.MIN_VALUE, Integer.MAX_VALUE] 范围。

这不太适合 long，因为 double 的精度小于 long，但如果精度不那么重要，则可以就足够了。

Answer 4

让我们从一个带有注释的简单形式开始：

long saturatedAdd(long x, long y) {
    long r = x + y;

    // Addition is safe from overflow if x and y have different signs
    if ((x < 0) != (y < 0)) {
        return r;
    }

    // Result has overflowed if the resulting sign is different
    if ((r < 0) != (x < 0)) {
        return x < 0 ? Long.MIN_VALUE : Long.MAX_VALUE;
    }

    // Otherwise result has not overflowed
    return r;
}

虽然使用这个实现没有任何问题，但接下来只是为了论证而尝试对其进行微观“优化”。

(x < 0) != (y < 0) 可以更改为 (x ^ y) < 0 本质上是符号位的按位XOR。

    // Addition safe from overflow if x and y have different signs
    if ((x ^ y) < 0) {
        return r;
    }

    // Result has overflowed if resulting sign is different
    if ((r ^ x) < 0) {
        return x < 0 ? Long.MIN_VALUE : Long.MAX_VALUE;
    }

此外，我们可以通过编写 (x ^ y) (x ^ y) 来强制将两个 if 放在一起。 0 || (r ^ x) >= 0 甚至 ((x ^ y) | ~(r ^ x)) 0 。此时它不再可读：

    if (((x ^ y) | ~(r ^ x)) < 0) {
        return r;
    }
    return x < 0 ? Long.MIN_VALUE : Long.MAX_VALUE;

我们可以从 Math.exactAdd() 中获取提示，并将 if 转换为 ((r ^ x) & ( r ^ y)) < 0 。它并没有提高可读性，但看起来“很酷”并且更加对称：

    if (((r ^ x) & (r ^ y)) < 0) {
        return x < 0 ? Long.MIN_VALUE : Long.MAX_VALUE;
    }
    return r;

唷，这有点飞跃了。本质上，它检查结果是否与两个输入具有不同的符号，只有当两个输入具有相同的符号并且结果符号不同于那个。

接下来，将 1 添加到 Long.MAX_VALUE 会得到 Long.MIN_VALUE：

    if (((r ^ x) & (r ^ y)) < 0) {
        return Long.MAX_VALUE + (x < 0 ? 1 : 0);
    }
    return r;

当 x x 时导出 1 的另一种方法。 0 是将符号位用作1。

    if (((r ^ x) & (r ^ y)) < 0) {
        return Long.MAX_VALUE + (x >>> (Long.SIZE - 1));
    }

最后，为了对称性，在位移中使用 r 而不是 x，得到：

    long r = x + y;
    if (((r ^ x) & (r ^ y)) < 0) {
        return Long.MIN_VALUE - (r >>> (Long.SIZE - 1));
    }
    return r;