9

Javaで2つの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で飽和加算を行う方法は？

4

4 に答える 4

5

数字の符号に基づいて、4つのケースに分けることができるはずです。数字の1つがゼロの場合、答えはもう1つの数字です。1つが正で、もう1つが負の場合、オーバーフローまたはアンダーフローすることはできません。両方が正の場合、オーバーフローすることしかできません。両方が負の場合、アンダーフローのみが可能です。

最後の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;
}
于 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には適していませんが、精度がそれほど重要でない場合は、それで十分です。doublelong

于 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) < 0XOR

    // 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で、あるいは。でさえ、2つを強制的に組み合わせることができました((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_VALUELong.MIN_VALUE

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

いつ1つを導出する別の方法x < 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;
于 2018-04-10T13:15:36.057 に答える