rotate_left_shift(x, 1) - x の最適化

uint32_t x に対して掲題の計算を行いたい。

rotate shift 命令のないプロセッサの場合は

((x << 1) | (x >> 31)) - x

を計算することになり四命令 (<<, |, >>, +) が必要となる。しかしこの演算は

x + (x >> 31)

と等価であるので後者であれば二命令 (>>, +) で実現できて効率が良い。

実際に等価である事は次のようにして確認できる。基本的なアイデアは x を上位 1 bit と下位 31 bit に分けて考えることである。

演算子 | の左右の有効ビットは左が上位 31 bit で右が下位 1 bit であるので重なりがない。よって | を + に置き換えられる。

((x << 1) + (x >> 31)) - x

加法は結合法則と交換法則を持つので外側の括弧を外して演算の順序を入れ替えても良い。

(x << 1) - x + (x >> 31)

真ん中の x を下位 31 bit と上位 1 bit に分ける。

(x << 1) - (x & 0x7FFF FFFF) - (x & 0x8000 0000) + (x >> 31)

前の二項は x の下位 31 bit の二倍から x の下位 31 bit を引いたものなので x の下位 31 bit に等しい。

(x & 0x7FFF FFFF) - (x & 0x8000 0000) + (x >> 31)

最上位ビットのみの数値の引き算は足し算と等しい。

(x & 0x7FFF FFFF) + (x & 0x8000 0000) + (x >> 31)

前の二項は x そのものである。

x + (x >> 31)