符号付き整数を 2 冪で割るときに右算術シフトを使ってしまって痛い目にあったことのある皆さんこんにちは。僕はあなたの仲間です。
コンピュータで割り算を行うのは一般に重いので、できるだけシフト等の軽い操作で済ませたいですよね。
最近のコンパイラは賢いので適当に書けば最適化してくれますが、何かしらの事情で自分で最適化しなければならいないときのためにやり方を紹介しておきます。
C99 で 32 ビット符号付き整数 x を 1<<n で割ることを考えます。
符号なし整数なら二冪の割り算 x/(1<<n) と右シフト x>>n は一致するのですが、符号あり整数については、割り算は 0 方向への切り捨てなのに対して、右算術シフトは切り下げとなります。
例えば (-3) / 2 の結果が -1 なのに大して (-3) >> 1 の結果は -2 です。
これは困りました。
簡単な対策として、x が負のときシフトを行う前に (1<<n)-1 を足すという方法があります。
こうすると、負の数のとき切り上げになり、割り算と同じになります。
ですが、if は一般に重いので、できるだけ使わずに済ませたいです。
そこで、全体として以下の手順を踏みます
xを31だけ右算術シフトしたものをyとする。yを32-nだけ右論理シフトしたものをzとする。xにzを足す。xをn右論理シフトする。
1, 2 が重要です。これによって z は x が正のとき 0 に、負のとき (1<<n)-1 になっています。
たとえば n=6 のとき
x = 0xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx y = 00000000000000000000000000000000 z = 00000000000000000000000000000000 x = 1xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx y = 11111111111111111111111111111111 z = 00000000000000000000000001111111
となっています。
正の数のときは最上位ビットが 0 なので、算術シフトによって 0 が引き出され全て 0 で埋まります。論理シフトをしても結果は変わりません。
対して負の数のときは最上位ビットが 1 なので、算術シフトによって 1 が引き出され全て 1 で埋まり、続いて論理シフトによって上位ビット 32-n ビットが全て 0 で埋まります。 1 は全部で n 個並んでいるのでこの値は (1<<n)-1 となります。
例えば以下のように実装できます。
C99 では論理シフトになるか算術シフトになるかは処理系依存であることに注意してください。
上記のコードは gcc 5.4.0 で動作を確認しています。
おまけ
ちなみに最近のコンパイラでも、ここで紹介した感じになります。
以下は clang 3.8.0 で x / 64 を MIPS にコンパイルした結果（の一部）です。
sra $2, $1, 31 srl $2, $2, 26 addu $1, $1, $2 sra $1, $1, 6
最後に
何か間違いや質問などがあればお願いします。
最後まで読んでいただきありがとうございました。
参考文献
[1] Henry S. Warren. (2012). Hacker’s Delight (2nd Edition)
