9

如何long在 Java 中添加两个值，以便如果结果溢出则将其限制在范围内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;
}

或者

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

4

4 回答 4

5

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

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

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;
}
于 2010-04-13T19:18:02.283 回答
4

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

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;
}
于 2010-04-13T21:00:42.913 回答
2

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

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

x和y被添加为double, 并且投射到int将饱和到[Integer.MIN_VALUE, Integer.MAX_VALUE]范围。

这不适合longs，因为精度double小于long，但如果精度不那么重要，它就足够了。

于 2014-07-13T23:57:38.563 回答
0

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

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

if此外，我们可以通过写(x ^ y) < 0 || (r ^ x) >= 0甚至将这两个 s 强行放在一起((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 < 0是将该符号位用作一个。

    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;
于 2018-04-10T13:15:36.057 回答