1

私は次のようなcの式を持っています：

X = (a * X) / b;

これは、で再スケーリングXするために使用されa/bます。ただしX、16ビットのunsigned intであり、withの乗算aは簡単にオーバーフローする可能性があります。正確な結果が得られる整数だけを使用してこの計算を行うにはどうすればよいですか。

もちろん浮動小数点演算を使用することもできますが、この操作が浮動小数点ハードウェアのないプロセッサで機能する可能性が高くなります。

編集：aとbは両方とも32ビットの符号なし整数であると言うのを忘れました。さて、私の答えは、右シフトaしbて、両方が16ビットに収まるまでです。その方法a * Xは最大32ビットであり、最終的な計算は正確です。

4

2 に答える 2

4

次のように書き直すことができます。

X = (a/b)*X + (a%b)*(X/b) + (a%b)*(X%b)/b

それらのいずれかがオーバーフローしないことを確認できる場合（最初はほぼ結果、2番目は結果より少なく、3番目の配当は約b^2）。

なぜそれが有効なのですか（オーバーフローが発生しない場合、/は通常の除算、div整数除算を意味します）：

X div Y =def floor(X/Y)
X =def (X div Y) * Y + X mod Y

(X*Y) div Z = floor(X*[(Y div Z) * Z + Y mod Z] / Z)
  = floor(X*(Y div Z)*Z/Z + X*(Y mod Z)/Z)
  = X*(Y div Z) + X*(Y mod Z) div Z

ここで、これを2回使用すると（演算子のCの意味で）：

X = (a*X)/b = X*(a/b) + X*(a%b)/b =
            = X*(a/b) + (a%b)*(X/b) + (a%b)*(X%b)/b

しかし、可能であれば、より高い精度で計算することをお勧めします

X = ((int)X*a)/b
于 2012-04-23T11:40:51.123 に答える
3

aたとえば、次のように、より大きなデータ型にプロモートできます。

X = ((long)a * X) / b;
于 2012-04-23T11:44:32.917 に答える