6

ビットシフト操作を実行して、ビットシフトして乗算するなど、さまざまなことを実行できることを理解しているため、mod操作の背後にあるロジックを理解したいと思っています。

分割ができなくなるまで分割し続ける再帰アルゴリズムを使用する方法がありますが、これは効率的ではないようです。

どんなアイデアも役に立ちます。前もって感謝します！

4

4 に答える 4

14

簡単なバージョンは次のとおりです。定数による除算であるかどうか（pdf）、チェックする例外があるかどうか（たとえば、0によるモジュロ）、負の数が処理されるかどうか、およびどのように処理されるか（これは怖いですC++ に関する質問) など...

R は、符号なし整数について適切で簡潔な回答を提供しましたが、C に精通していないと理解するのは困難です。

R によって明らかにされた手法の要点は、倍数がqなくなるまで、倍数を取り除くことですq。単純なループで単純にこれを行うことができます。

while (p >= q) p -= q; // One liner, woohoo!

コードは短いかもしれませんが、p の値が大きく、q の値が小さい場合、これには非常に長い時間がかかる場合があります。

一度に1 つずつ削除するよりもq、一度に多くの を削除する方がよいでしょうq。q実際には、できるだけ多くの を削除したいことに注意してください。つまり、多くfloor(p/q)のを削除しqます...実際、これは有効な手法です。符号なし整数の場合、p % q == p - (p / q) * q. (符号なし整数除算は切り捨てであることに注意してください。)

しかし、除算と剰余演算は非常に密接に関連しているため、これはほとんど不正行為のように感じられます。(実際、ハードウェアが除算をネイティブにサポートしている場合、除算と剰余の計算がサポートされていることがよくあります。これは、それらが非常に強く関連しているためです。)

q割り算ができないと仮定すると、取り除ける 1 より大きい倍数をどのように見つければよいでしょうか。ハードウェアでは、固定シフト操作は安価であり (実際には無料ではないにしても)、概念的には 2 の負でない累乗による乗算を表します。たとえば、ビット文字列を 3 だけ左にシフトすることは、8 を乗算することと同じです (つまり、2^3)。右側に 3 つのゼロを追加して 2 進数で '101' をシフトすると ('101000' になります)、結果は 10 進数で 50、つまり 8 の 5 倍になります。

同様に、シフト操作はソフトウェア操作として非常に安価であり、それらをサポートしていないコントローラーをすばやく見つけるのに苦労するでしょう. (ARM などの一部のアーキテクチャでは、シフトを他の命令と組み合わせて、多くの時間を「フリー」にすることさえできます。)

これらのシフト操作で武装した (抵抗できなかった) 場合、次のように進めることができます。

  1. を乗じqても 未満になる最大の 2 のべき乗を求めpます。
  2. 2 の最大の累乗から最小の順に作業し、q各 2 の累乗を掛け、それが の残りの部分よりも小さい場合は、 の残りの部分pから引きpます。
  3. あなたが残したものは何でも残りです。

なぜこれが機能するのですか？floor(p / q)最終的に、2 のべき乗をすべて減算すると、実際には!になることがわかります。私の言葉を鵜呑みにしないでください。同様の知識は非常に長い間知られています。

Rの答えを分解する：

#define HI (-1U-(-1U/2))

これにより、最高値のビットのみが設定された符号なし整数が効果的に得られます。

unsigned i;
for (i=0; !(HI & (q<<i)); i++);

qこの行は、符号なし整数をオーバーフローする前に乗算できる最大の 2 のべき乗を実際に検出します。これは厳密には必要ではありませんが、必要な実行時間が長くなる以外に結果は変わりません。

この行の C-isms に慣れていない場合:

  1. (q<<i)の左ビット シフトiです。これは 2^ を掛けることと同じであることを思い出してくださいi。
  2. HI & (q<<i)ビットごとの AND を実行します。最上位ビットのみが設定されているため、最上位ビットが非ゼロになるのに十分な大きさHIの場合にのみ非ゼロ値になります。(q<<i)左にもう 1 シフトすると、整数オーバーフローが発生します。
  3. !(HI & (q<<i))(HI & (q<<i))がゼロの場合は「真」、それ以外の場合は「偽」です。

do { if (p >= (q<<i)) p -= (q<<i); } while (i--);

これは単純な減少ループdo { .... } while (i--);です。ポストデクリメントが使用されてiいるため、ループが実行され、iがゼロでないかどうかを確認しi、 から 1 を減算し、前のチェックの結果がtrue継続する場合に注意してください。これには、 が 0 のときにループが最後に実行されるというプロパティがあります。i乗算されていない のコピーを取り除く必要がある場合があるため、これは重要ですq。

if (p >= (q<<i))i2^ *qが よ​​り小さいか等しいかどうかをチェックしpます。ある場合は、p -= (q<<i)それを取り除きます。

残りは残ります。

于 2013-06-26T19:50:49.420 に答える
2

R..が示唆するように、シフトを使用したハードウェア命令と実装に加えて、逆数乗算もあります。

この手法は、 の右辺が%コンパイル時に既知の定数である場合に使用できます。
逆数乗算は除算を実装するために使用されますが%、公式に基づいて、それを使用するのは簡単a%b == a-(a/b)*bです。

于 2013-06-26T19:27:06.287 に答える
0

オプティマイザーの賢さによっては、基数 2 を法とするショートカットがあります。たとえば、a % 32として実装できますa & 31。一般的に、a % (2^N) == a & (2^N -1). これは除算に比べて非常に高速です。ほとんどの除算器 (すべてのハードウェア) は、結果の各ビットを計算するために少なくとも 1 サイクルを必要としますが、論理 AND は (パイプラインで) 数サイクルの演算にすぎません。

編集:これaは署名されていない場合にのみ機能します!

于 2013-07-01T16:38:49.067 に答える