06/10/10 11:35:36
その割り算は>>532のことか？
1ワードが無限のビット長だとすると、原理的には
x / 100 == (x / 100) << 32 >> 32
という当たり前の恒等式を巧みに利用する。
ここでは 2のx乗 を 2^x と表現するので、そのつもりで。
x回の左シフトは、算術的には *(2^x) を意味する。
その性質を利用すると、右辺は
=> x / 100 * (2^32) >> 32
=> x * ((2^32) / 100) >> 32
と変形できる。最適化のとき予め (2^32) / 100 を計算しておく。
この定数をnとおくと、除算の商は (x * n) >> 32 で求めることができる。
つまり定数の除算は乗算とシフトに変換できるというわけ。
実際はビット長が無限大ということはないし符号も考慮しないといけないので
これよりも少し複雑な処理になる。