16388


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

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

[code]

    // 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);
        }
    }
    
[/code]


CC BY-SA 3.0
2015-05-27T12:54:18.027
10691
2015-09-09T03:58:12.797
8870
question
c# アルゴリズム .net
longの飽和演算を行うアルゴリズムを教えてください


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


CC BY-SA 3.0
2015-05-27T13:29:51.843
10694
2015-05-27T13:29:51.843
5750
10691
answer


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

**追記**

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

[code]

    long c = (a > (long.MaxValue - b) ? long.MaxValue : a + b);
    
[/code]

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


CC BY-SA 3.0
2015-05-27T14:07:11.437
10695
2015-09-09T03:43:30.283
2015-09-09T03:43:30.283
7283
7283
10691
answer


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

[code]

    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;
    }
    
[/code]

なお、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.

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


CC BY-SA 3.0
2015-05-27T14:27:21.613
10698
2015-09-09T03:58:12.797
2015-09-09T03:58:12.797
4236
4236
10691
answer


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

[code]

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


CC BY-SA 3.0
2015-05-28T00:04:31.497
10700
2015-05-28T00:04:31.497
7282
10691
answer


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

[code]

    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);
    }
    
[/code]


CC BY-SA 3.0
2015-09-08T13:53:11.080
16388
2015-09-08T14:41:07.960
2015-09-08T14:41:07.960
8870
8870
10691
answer