[迷信] 2の累乗による割り算と右シフトは等価

多くの場合、実際に試してみればすぐに分かることですが,2n による割り算と右シフトは、常に等価になるとは限りません。しかし、この問題は規格上処理系定義の要素が複雑に絡み合っているため、注意深く考えないと全体像をとらえることができません。

まずは簡単なところから手を付けることにしましょう。被除数が正の場合です(符号無し整数の場合もこれに含まれます)。正整数 / 2n の計算は,正整数 >> n に単純に置き換えることができます。端数は常に切り捨てられるため、これは簡単です。

次に、被除数が負の場合を考えます。ここで、符号付き整数の右シフトが算術シフトにならないような処理系は論外ですので、議論の対象から外します。この時点で、2n による割り算と右シフトが常に等価ではないことが分かりました。なお、負整数の内部表現が符号ビット&絶対値の場合の算術シフトは、符号ビットの状態を保持したまま、値ビットだけをシフトするものと考えます。

-1 を 2 で割った場合、C99では 0 になります。しかし、負整数の内部表現が 2 の補数の場合には、-1 を算術右シフトすると -1 になります。1 の補数および符号ビット&絶対値の場合は -0 になります。ただし、これが +0 に置き換わるかどうかは処理系に依存しますし、-0 に相当するビットパターンがトラップ表現になる場合もあり得ます。いずれにせよ、2 で割った場合と 1 ビット算術右シフトした場合は常に等価ではありません。

そして、C90やC++では、-1 / 2 が 0 になるか -1 になるかは処理系定義ですので、それによっても状況が変わってきます。

この記事のトラックバックURL:

http://www.kijineko.co.jp/trackback/491