与えられた数値x、yおよびについて、C でn計算したいと思います。この例を見てください。x-y mod n
int substract_modulu(int x, int y, int n)
{
return (x-y) % n;
}
である限りx>y、私たちは大丈夫です。ただし、それ以外の場合、剰余演算はundefinedです。
と考えることができますx,y,n>0。結果を正にしたいので、もし(x-y)<0, then((x-y)-substract_modulu(x,y,n))/ nは整数でなければなりません.
そのためにあなたが知っている最速のアルゴリズムは何ですか? ifandの呼び出しを回避するものはありoperator?ますか?
多くの人が指摘しているように、現在の C および C++ 標準では、 はおよびx % nの値に対して実装定義ではなくなりました。が未定義の場合は未定義の動作です[1]。また、整数オーバーフローの場合の未定義の動作です。これは、 と の符号が異なる場合に発生する可能性があります。xnx / nx - yxy
したがって、一般的な解決策の主な問題は、除算または減算で整数オーバーフローを回避することです。xandyが非負で正であることがわかっている場合、オーバーフローとゼロ除算は不可能であり、それが定義されnていると自信を持って言えます。(x - y) % n残念ながら、x - y負になる可能性があります。その場合、%演算子の結果は負になります。
結果が正であることがわかっている場合、負の結果を修正するのは簡単nです。無条件に追加nして別のmodulo操作を行うだけです。分岐よりも除算の方が速いコンピューターを使用していない限り、これが最善の解決策である可能性は低いです。
条件付きロード命令が利用できる場合 (最近ではかなり一般的です)、コンパイラはおそらく次のコードでうまく機能しますx,y ≥ 0 ∧ n > 0。
((x - y) % n) + ((x >= y) ? 0 : n)
たとえば、gcc は私のコア I5 用に次のコードを生成します (ただし、古生代以外の Intel チップで動作するのに十分な汎用性があります)。
idivq %rcx
cmpq %rsi, %rdi
movl $0, %eax
cmovge %rax, %rcx
leaq (%rdx,%rcx), %rax
元気にブランチフリーです。(通常、条件付き移動は分岐よりもはるかに高速です。)
これを行う別の方法は次のとおりです (ただし、関数signを記述する必要があります)。
((x - y) % n) + (sign(x - y) & (unsigned long)n)
ここで、signは引数が負の場合はすべて 1 で、そうでない場合は 0 です。 sign の可能な実装の 1 つ ( bithacksから適応) は次のとおりです。
unsigned long sign(unsigned long x) {
return x >> (sizeof(long) * CHAR_BIT - 1);
}
これは移植性があります (負の整数値を unsigned にキャストすることが定義されています) が、高速シフトを欠くアーキテクチャでは遅くなる可能性があります。以前のソリューションよりも高速になる可能性は低いですが、YMMV. TIAS。
これらのどちらも、整数オーバーフローが発生する可能性がある一般的なケースでは正しい結果を生成しません。整数オーバーフローを処理するのは非常に困難です。(特に厄介なケースの 1 つは ですn == -1。ただし、それをテストして を使用せずに 0 を返すことはできます%。) また、負のモジュロの結果に対する好みを決定する必要がありますn。個人的にx%nは、 が 0 であるか、または と同じ符号を持つ定義を好みnます。
Tom Tanner によって提案された 3 モジュロ ソリューションは、そうでなく、オーバーフローしない場合にn機能します。またはがの場合は失敗し、 の代わりに使用する単純な修正はが の場合に失敗します。絶対値が大きいケースは比較に置き換えることができますが、多くのコーナー ケースがあり、標準では 2 の補数演算が必要ないという事実によってより複雑になり、コーナー ケースが何であるかを簡単に予測することはできません。 [2]。-1n + nn == -1xyINT_MINabs(n)nnINT_MINn
最後に、いくつかの魅力的なソリューションは機能しません。の絶対値を取ることはできません(x - y)。
(-z) % n == -(z % n) == n - (z % n) ≠ z % n（z % nたまたまでない限りn / 2）
また、同じ理由で、モジュロの結果の絶対値を取ることはできません。
(x - y)また、 unsignedにキャストすることはできません。
(unsigned)z == z + 2k (for some k) if z < 0
(z + 2k) % n == (z % n) + (2k % n) ≠ z % nそうでもなければ(2k % n) == 0
[1]x/nとx%nはどちらも定義されていませんn==0。しかし、 が「表現できない」場合 (つまり、整数のオーバーフローがあったx%n場合) も未定義ですx/n。2 の補数のマシン (つまり、関心のあるすべてのマシン) で発生します。この場合、 が未定義であるべき理由は明らかですが、 の場合は、その値が (数学的に) であるため、未定義であることがわずかに少なくなります。xn == -1x/nx%n0
[2] 浮動小数点演算の結果を予測することの難しさについて不平を言うほとんどの人は、真に移植可能な整数演算コードを書くことに多くの時間を費やしていません:)
ifなしで未定義の動作を避けたい場合は、次のようにします
return (x % n - y % n + n) % n;
効率はモジュロ演算の実装に依存しますが、関与ifするアルゴリズムはかなり高速になると思います。
xまたは、 andyを unsigned として扱うこともできます。その場合、関与する負の数はなく、未定義の動作もありません。
C++11 では、未定義の動作が削除されました。あなたが望む正確な動作に応じて、そこに固執することができます
return (x-y) % n;
完全な説明については、この回答を読んでください：
https://stackoverflow.com/a/13100805/1149664
n==0 の場合、または使用している型に xy を格納できない場合は、未定義の動作が引き続き発生します。
と仮定する0 <= x < nと0 <= y < n、どう(x + n - y) % nですか？その場合、x + n は確かに y よりも大きくなり、y を減算すると常に正の整数になり、最終的な mod n は必要に応じて結果を減らします。
分岐が問題になるかどうかは、ある程度 CPU に依存します。abs( MSDNの)ドキュメントによると、固有の動作があり、ボトルネックにはならない可能性があります。これはテストする必要があります。
無条件に計算したくない場合は、Bit Twiddling Hacks サイトから適応できるいくつかの優れた方法があります。
int v; // we want to find the absolute value of v
unsigned int r; // the result goes here
int const mask = v >> sizeof(int) * CHAR_BIT - 1;
r = (v + mask) ^ mask;
ただし、ハードウェア ターゲットとテストに関する詳細情報がなければ、これがあなたの状況に役立つかどうかはわかりません。
好奇心から、これを自分でテストする必要がありました。コンパイラによって生成されたアセンブリを見ると、 の使用に実際のオーバーヘッドがないことがわかりますabs。
unsigned r = abs(i);
====
00381006 cdq
00381007 xor eax,edx
00381009 sub eax,edx
以下は、Bit Twiddling Site によると特許を取得していない上記の例の代替形式です (Visual C++ 2008 コンパイラで使用されているバージョンは特許を取得しています)。
私の回答を通して、私は MSDN と Visual C++ を使用してきましたが、正常なコンパイラはすべて同様の動作をすると思います。
ここでは実際にはそうではないと推測しますが、モジュロをとっている値が 2 の累乗である場合は、"AND" メソッドを使用する方がはるかに高速であることに言及したいと思います (I' m は xy を無視し、xy はここでは方程式の一部ではないため、単一の x に対してどのように機能するかを示します):
int modpow2(int x, int n)
{
return x & (n-1);
}
あなたのコードが何か馬鹿なことをしないようにしたい場合は、追加することができますASSERT(!(n & n-1));- これは、1 つのビットのみが設定されていることを確認しますn(つまりn、2 の累乗です)。