多くのCPUには、算術シフト演算命令が含まれています。そのため、多くのコンパイラは、符号付き整数に対する右シフトを算術シフトにコンパイルします。 しかし、C言語において、符号付き整数を右シフトした場合の挙動は処理系定義です。処理系定義というのは、以下のようなものです。
よって、移植性のあるコードを書くためには、符号付き整数に対して右シフトをすることは避けたいところです。
符号付き整数に対する右シフトと等価なコードは、if文の利用等により、書くこと自体はできます。
しかし、せっかくなので、CPUに存在する算術シフト命令を使える方法を考えてみます。
割り算を使う方法
定数での割り算の場合、コンパイラは算術シフト命令へ最適化することがあります。 これを利用できないかと考えてみます。
右シフトの代わりに除算を使う方法は、負数に対して異なる結果を与えるため不適です。 よって、オペランドの正負によって場合分けが必要です。
いろいろとif文の条件を工夫してコンパイラにヒントを与えてみましたが、コンパイラに算術シフト命令を吐かせることはできませんでした。
どうやら、定数除算を算術シフト命令に変換する最適化は、コード丸ごとの置換であり、最適化のかなり後ろの段階で行われているようです。
符号なし整数を利用する方法
clangの場合、以下のコードでやりたいことを見抜いてくれます。
std::int64_t sar( std::int64_t x ) {
std::uint64_t y = x;
y += 1ull << 63;
y >>= 1;
y -= 1ull << 62;
return y;
}
このコードは、yをstd::int64_tにキャストする際にオーバーフローする可能性があり、完全とは言えません。
分岐を行うことでオーバーフローを防ぐ、完全なコードは以下になります。std::bit_castを使うのも悪くないでしょう。
std::int64_t sar( std::int64_t x ) {
static constexpr std::int64_t min = -0x7fffffffffffffff - 1;
static constexpr std::uint64_t bias = 0x8000000000000000;
std::uint64_t y = x;
y += bias;
y >>= 1;
y -= bias >> 1;
return y < bias ? static_cast<std::int64_t>(y)
: static_cast<std::int64_t>(y-bias) + min;
}
これらのコードは無意味に複雑ですが、最適化オプション-O1などでコンパイルすれば単なる算術シフト命令になります（x86_64向けclangのいろんなバージョンで確認）。
