3

こんにちは、シフトと加算/減算のみを使用して符号なし定数で除算しようとしています-乗算であれば問題ありませんが、除算に少し困惑しています。

たとえば、定数除数が 192 で、被除数が 8000 であるとします。

「完全な結果」 y = 8000/192 = 41 (小数ビットを保持していないと仮定)

y = 8000 >> 8 ... 31 y = 8000 >> 7 ... 62

しかし、どうすればより正確な解を得ることができるでしょうか?

どうもありがとう！

4

3 に答える 3

9

もっと洗練された方法があることはほぼ間違いありませんが、始めるにはこれで十分です。

通常、この方法での除算は、逆数を掛けることによって行われます。つまり、最初に掛けてから右シフトします。

（注：乗算はシフトと加算によって達成できることを覚えておいてください（たとえばn * 3 = (n*2) + (n*1) = (n << 1) + (n) )、ここでは乗算を使用するだけです。あなたの質問は「シフトと加算」と言っており、乗算の省略表現の使用を正当化しています）

以下の例では、例を使用して概念を説明しようとしています。特定のケースでは、次のような問題を検討する必要があります

  1. sign (以下では unsigned int を使用しています)

  2. オーバーフロー (以下では、中間値を保持するために 32 ビットの符号なし long を使用していますが、小さい uC を使用している場合は、それに応じて調整してください

  3. 丸め (たとえば、9/5 は 1 または 2 を返す必要がありますか? C では 1 ですが、正解に近いので 2 が必要になる場合がありますか?)

  4. できる限り (利用可能なビット)、除算の前にすべての乗算を行います (切り捨てエラーを最小限に抑えます)。繰り返しますが、オーバーフローに注意してください。

前述したように、以下を読んで概念を理解してから、ニーズに合わせて調整してください。

192 で割ることは 1/192 を掛けることと同じであり、これは (64 * 3) で割ることと同じです。1/3 の正確な (有限の) バイナリ表現はないため、0x5555/(1 << 16) で概算しています。

192 で割るには、64 で割ってから 3 で割ります。3 で割るには、0x5555 を掛けて右に 16 シフトします (または 0x55 を掛けて >> 8、または...)。

//                8000/192          =
//                ((8000/64)/3)     =
//                ((8000 >> 6) / 3) =
//                (((8000 >> 6) * 0x5555) >> 16)
//                (((8000 * 0x5555) >> 22

括弧は意図的なものであることに注意してください。第 2 項が 0 で積が 0 になるため、 計算する必要はありません。良くありません。(8000 * (0x5555/(1 << 16))

したがって、コードのワンライナーは次のようになります。

 printf("Answer:  %lu\n", ((8000UL * 0x5555UL) >> 22));

これは 41 を生成します。これは8000/192、42 が「より近い」ものであっても、「C」が に対して生成するものです。LSB をチェックすることで、必要に応じて丸めることができます。

このトピックについて論文を書くこともできますが、幸いなことに、私よりもはるかに賢い人がすでに持っています.

于 2011-02-03T20:24:51.597 に答える
5

任意の定数で最適化された除算を簡単に行うことができる定数除算ジェネレーターを開発しました。「Hacker's Delight」のアイデアを踏襲しています。

「kdiv」という名前のツールは、sourceforge で入手できます。

http://sourceforge.net/projects/kdiv/

于 2011-08-07T23:00:34.693 に答える
2

この種のことについては、ハッカーの喜びの本を見ます。私はコピーを持っていませんが、それとは別に、除数 192、つまり 0xC0 を見ると、上と下を 0x40 で割ることができます。シフト 8000>>6 = 125.8000/192 -> 125/ 3 ですが、その場合は 3 で割る必要があります。答えは 125/2 から 125/4 の間のどこかにあることがわかっています。これらの特定の数値では、125 は 0x7d または b1111101 であり、これは b100000 + 11101 の 3 倍であり、(3 倍 0x20) + (3 倍 8) + 5 なので、125/3 = 0x20 + 0x8 + (5/3) であり、5/3 は1 より大きいが 2 より小さいため、0x28+1 = 41 とすぐに判断されます。除数ビット パターンが分子ビット パターンの上位ビットに現れ続ける場合にのみ、シフトで減少し続けます。ハッカーが喜んでいるか、または他の同様の情報源がこの問題について何を言っているかはわかりませんが、

于 2011-02-03T16:09:24.923 に答える