代码之家 › 专栏 › 技术社区 › finnw

两个签名的Java“长”值的饱和加法

integer-overflow signal-processing math bit-manipulation java

finnw · 技术社区 · 15 年前

一加二怎么样 long Java中的值,以便如果结果溢出,则将其箝位到范围内。 Long.MIN_VALUE … Long.MAX_VALUE ?

为了增加整数,可以在 长的 精确并将结果转换回 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);
}

但是在 长的 没有更大的基元类型可以保存中间(未截取)和。

因为这是Java,我不能使用 inline assembly (特别是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中的性能。我认为它可以,但是我想对有分支和没有分支的方法进行基准测试。

相关: How to do saturating addition in C?

4 回复 | 直到 7 年前

M. Jessup 15 年前

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

只需对最后两个案例进行额外计算,看看是否会导致不需要的案例:

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

finnw 15 年前

以下是我尝试的无分支版本:

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

maaartinus 10 年前

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

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

x 和 y 添加为 double ,并铸造至 int 将饱和到 [Integer.MIN_VALUE, Integer.MAX_VALUE] 射程。

这不太适合 long s作为精度 双重的 小于 长的 但是如果精度不那么重要,它就足够了。

antak Jason 7 年前

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

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 甚至 ((x ^ y) | ~(r ^ x)) < 0 . 此时,它不再可读:

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

我们可以从 Math.exactAdd() 把它转过来 如果 进入之内 ((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;