こんにちはシフトと加算/減算のみを使って符号なし定数で除算しようとしています - これは乗算であれば問題ありませんが、部門によって困った。シフトを使った定数による除算と加算/減算
例えば、一定の除数は192であり、配当は8000
「完全な結果」Y = 192分の8000 = 41（私は小数ビットを保持していないよと仮定）
であると言うことができます言うことができますy = 8000 >> 8 ... 31 y = 8000 >> 7 ... 62
しかし、もっと正確な解決策を得るにはどうすればよいですか？
多くの感謝！
これはもっとエレガントな方法ですが、ここでは始めるには十分です。
通常、このような除算は、逆数を掛けること、すなわち、最初に乗算してから右にシフトすることによって行われる。
は（注：例えばn * 3 = (n*2) + (n*1) = (n << 1) + (n))（つまりmultplicationがシフトすることにより達成して追加することができます覚えているが、私はちょうどここに乗算を使用するつもりだあなたの質問は、「シフト&を追加」と私は）乗算の私の速記使用を正当化していました。以下の例で
、私は一例で概念を説明しようとしています。あなたの特定のケースでは、あなたがそのような（私は符号なしint型を使用してい
記号などの問題を検討したいと思います以下）
オーバーフロー（以下では、中間値を保持するために32ビットの符号なしlongを使用していますが、小さいuCを使用している場合はそれに応じて調整してください）
9/5は1または2を返しますか？
（使用可能なビット数）できるだけ、除算の前にすべての乗算を行います（切り捨てエラーを最小限に抑えるために）、Cで1を返します。 。再度、オーバーフローに注意してください。
私が言ったように、以下を読んでコンセプトを理解し、必要に合わせて調整します。
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
括弧は意図的なものです。あなた(8000 * (0x5555/(1 << 16)) 2番目の項が0で、製品が0になるため計算したくありません。
ので、コード内で1ライナーは、のようになります。これは、「C」は42が「近い」であっても、8000/192ために生じるであろうものである、41が得られます
printf("Answer: %lu\n", ((8000UL * 0x5555UL) >> 22));
。 LSBをチェックすることで、必要に応じて丸めることができます。
このトピックについては論文を書くことができますが、幸いにもsomeone much smarter than me already hasです。
問題はあなたが乗算されていますか？だけシフト、追加、サブ –
@ dwelchであるはずだ、第3段落をもう一度読んでください。それは（注： – Dan
私は、この種のことについてハッカーの喜びの本を見ます。私は私のコピーを持っていませんが、0x40で区切ることができるように、0xC0であるので、あなたの除数192を見ればそれとは独立しているので、8000 >> 6 = 125。8000/192→125 /しかし、あなたは3で割る必要があります。答えは125/2から125/4の間のどこかにあることがわかります。これらの特定番号125は、（3×0x20）+（3×8）+5の3倍の0x7dまたはb1111101であり、したがって125/3 = 0x20 + 0x8 +（5/3）であり、5/3はすぐに1より大きいが2より小さいので、0x28 + 1 = 41と決定されます。除数ビットパターンが分子ビットパターンの上位ビットに表示され続ける場合には、シフトを続けて減少し続けます。私は、ハッカーたちが喜んでいるか、他の同様の情報源がこの問題について言いますか、私はちょうどこれらの特定の数字についてこのパターンに気付いたことは知りません。
私は、任意の定数で簡単に最適化除算を与える定数除算ジェネレータを開発しました。 「Hacker's Delight」のアイデアに従います。
"kdiv" というツールはsourceforgeのに利用可能である：
さらに反射に答えは明らかである.... 192分の1 = 5.208x10^-3存在/ 2^8 + 1/2^10 + 1/2^12 ...となり、十分な精度に達するまで項が追加されます。 – trican
単なる注意：これは、最適化コンパイラが最適なアーキテクチャの場合、与えられた除数に対して完全最適化を使用してコンパイルを行い、出力を調べることができます。現代の最適化コンパイラは、与えられた計算でどんな種類の数学/ビット操作（もしあれば）が最速で実行されるかを決定する上で非常に優れています。 –
これは、数値の固定小数点表現による乗算と同等です。これは、実際の除算と同じ丸め動作をすることはないので、最適化コンパイラはおそらくそれをしません。 – phkahler