15

longのビット数で加減算の飽和演算を行いたいです。
検索してもSIMD関連の話題ばかり引っかかってしまいます。

int幅であればlongにキャストして演算後、intに戻すという手段を使えますが、longの場合BigIntegerを使用するというのは大げさな気がします。
効率のよいアルゴリズムがあれば教えて頂きたいです。

// SaturationLong
public struct SatLong
{
    public long Value;
    public SatLong(long value)
    {
        Value = value;
    }
    public static SatLong operator +(SatLong value1, SatLong value2)
    {
        // todo: saturation
        return new SatLong(value1.Value + value2.Value);
    }

    public static SatLong operator -(SatLong value1, SatLong value2)
    {
        // todo: saturation
        return new SatLong(value1.Value - value2.Value);
    }
}

5 件の回答 5

19

C# .NETということですが、Visual C++にはSafeIntライブラリというものが用意されています。これはura14hさんの書かれているように、演算結果が飽和するかどうかをチェックしながら演算を進めてくれるテンプレートライブラリです。
このアイデアをC#で飽和加算として表現するならこのような感じでしょうか。

static long Addition(long lhs, long rhs) {
    long tmp = unchecked(lhs + rhs);
    if (lhs >= 0) {
        if (rhs >= 0 && tmp < lhs)
            return long.MaxValue;
    } else {
        if (rhs < 0 && tmp > lhs)
            return long.MinValue;
    }
    return tmp;
}

なお、pgrhoさんの提案されているP/Invokeは呼び出しのコストがあるため計算全体をアセンブラで実装した方がよくなりもはやC#とは言えなくなりますし、h2so5さんの提案されているchecked及び例外を使用する方法も例外のコストが大きいのでソースコードのシンプルさはありますが実行効率は良くありません。


C#では剰余演算を行う事が定義されているのでしょうか?

そもそも専用のキーワードuncheckedが用意されている時点でC/C++言語とは状況が違います。手元にあった C#言語仕様 5.0 英語版から引用します。

7.8.4 Addition operator
In a checked context, if the sum is outside the range of the result type, a System.OverflowException is thrown. In an unchecked context, overflows are not reported and any significant high-order bits outside the range of the result type are discarded.

ということで演算結果から上位ビットが欠落するとのことです。

2
  • 1
    符号付き整数演算のオーバーフロー時の動作はC/C++では未定義ですが、C#では剰余演算を行う事が定義されているのでしょうか? (質問投稿者ではありませんが興味のある質問だったので)
    – alpha
    Commented 2015年9月9日 2:19
  • 1
    @alpha さん、回答を加筆しましたので確認いただけたらと思います。
    – sayuri
    Commented 2015年9月9日 3:58
5

例えば、value1 + value2がInt64.MaxValueを超える状況というのはvalue1がInt64.MaxValue - value2よりも大きいということなので、やりたい演算の前に逆の演算をして結果が収まるかを調べるという方法もあるように思います。

追記

加算を試しに書いてみました。

long c = (a > (long.MaxValue - b) ? long.MaxValue : a + b);

減算はaとbの符号の組み合わせで場合分けしないとダメかも、です。

2

Javaのサンプルですみません。C#でも同じじゃないかしら。。

long sum = a + b;
sum = ((((sum ^ a) & (sum ^ b))) >= 0L) ? sum : (a > 0 ? Long.MAX_VALUE : Long.MIN_VALUE);
1

効率を追求するのであればオーバーフロー時にはOFフラグが立つので、アセンブラで関数を書いてVirtualAllocやP/Invokeで読み込むのが良いのではないかと思います。

1

sayuri さんの回答を参考に、減算側もSafeIntライブラリを参考にしたものを記載します。

public static SatLong operator +(SatLong lhs, SatLong rhs)
{
    long tmp = unchecked(lhs.Value + rhs.Value);
    if (lhs.Value >= 0)
    {
        if (rhs.Value >= 0 && tmp < lhs.Value)
            return new SatLong(long.MaxValue);
    }
    else
    {
        if (rhs < 0 && tmp > lhs)
            return new SatLong(long.MinValue);
    }
    return new SatLong(tmp);
}

public static SatLong operator -(SatLong value1, SatLong value2)
{
    long tmp = unchecked(lhs.Value - rhs.Value);
    if (lhs.Value >= 0 && rhs.Value < 0 && tmp < lhs.Value)
        return new SatLong(long.MaxValue);
    if (rhs.Value >= 0 && tmp > lhs.Value)
        return new SatLong(long.MinValue);
    return new SatLong(tmp);
}

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。