遊びにはいくつかのアイデアがあります。
まず、2 つの短い整数を乗算して長い積を生成します。16 ビットの「半分」の乗算による 2 つの 32 ビット整数の符号なし乗算を考えます。それぞれが 32 ビットの積を生成し、合計の積は 64 ビットです。
a * b = (a_hi * 2 16 + a_lo) * (b_hi * 2 16 + b_lo) =
a_hi * b_hi * 2 32 + (a_hi * b_lo + a_lo * b_hi) * 2 16 + a_lo * b_lo.
ここで、符号付き乗算が必要な場合は、符号なし乗算から (たとえば上記から) 構築できます。
a < 0 かつ b >= 0 とすると、a *符号付きb は等しくなければなりません
2 64 - ((-a) *符号なしb)、ここで
-a = 2 32 - a (これは 2 の補数であるため)
ああ、
a *符号付きb =
2 64 - ((2 32 - a) *符号なしb) =
2 64 + (a * unsigned b) - (b * 2 32 ) ここで、64 ビットのみを使用しているため、2 64は破棄できます。
まったく同じ方法で、a >= 0 および b < 0 に対して a * signed b を計算でき、対称的な結果を取得する必要があります。
(a *符号なしb) - (a * 2 32 )
同様に、a < 0 および b < 0 の場合、符号なし乗算の上に符号付き乗算を次のように構築できることを示すことができます。
(a *符号なしb) - ((a + b) * 2 32 )
したがって、最初に a と b を符号なしで乗算し、次に a < 0 の場合は積の上位 32 ビットから b を減算し、b < 0 の場合は積の上位 32 ビットから a を減算します。
32 ビットの符号付き整数を乗算して 64 ビットの符号付き積を取得できるようになったので、最終的に分数に目を向けることができます。
ここで、a と b の 32 ビットのうち、N ビットが小数部に使用されるとします。つまり、a と b を単純な整数として見ると、それらが実際に表すものよりも 2 N倍大きくなります。たとえば、1.0 は 2 N (または 1 << N) のように見えます。
したがって、このような整数を 2 つ掛けると、その積は 2 N *2 N = 2 2*N倍になり、たとえば 1.0 * 1.0 は 2 2*N (または 1 << (2*N))。IOW、単純な整数乗算では、小数ビットの数が 2 倍になります。積に被乗数と同じ数の小数ビットを持たせたい場合は、どうしますか? 積を 2 Nで割ります(または算術的に N 桁右にシフトします)。単純。
念のため、いくつかの注意事項...
C (および C++) では、変数に含まれるビット数と同じかそれ以上のビット数だけ、変数を左または右に合法的にシフトすることはできません。コードはコンパイルされますが、期待どおりに動作しません。したがって、32 ビット変数をシフトしたい場合は、0 から 31 桁分左または右にシフトできます (32 ではなく 31 が最大です)。
符号付き整数を左にシフトすると、結果が合法的にオーバーフローすることはありません。すべての符号付きオーバーフローは、未定義の動作を引き起こします。したがって、署名なしに固執することをお勧めします。
負の符号付き整数の右シフトは実装固有です。算術シフトまたは論理シフトのいずれかを実行できます。どちらか、それはコンパイラに依存します。したがって、2 つのうちの 1 つが必要な場合は、コンパイラがそれを直接サポートしていることを確認するか、他の方法で実装する必要があります。