Java中有符号长整型值的饱和加法

Question

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

对于添加int，可以使用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中进行饱和加法？

- finnw

---

实际上，您可以使用汇编语言，只要将其包装在JNI或JNA中即可。看到所提议解决方案之间的性能比较将是很好的。 - janislaw

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

- M. Jessup

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

- finnw

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，但如果精度不那么重要，它就足够了。

- Lajos Molnar

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) < 0 || (r ^ x) >= 0 或者甚至是 ((x ^ y) | ~(r ^ x)) < 0 来强制将这两个 if 结合在一起。但是到了这个地步，代码已经不易阅读了。

    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 < 0 时，另一种得到 1 的方法是使用 符号位。

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

最后，为了对称起见，将那个位移中的x改为使用r，得到：

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

- antak