「不定だ・・・。犀川創平君。君の方程式の解は、今や不定だ」

森博嗣 - 『笑わない数学者―MATHEMATICAL GOODBYE』

C言語には、ビットシフト演算子というものがあります。左シフト演算子(<<)と右シフト演算子(>>)です。同じビット演算でも、ビット単位の論理和(|)や論理積(&)、NOT(~)等はの方は、フラグ型の変数の処理で使われる事が多い気がしますが、ビットシフトの方は使用されるケースはあまりないかもしれません。

さて、このビットシフト演算子で時々問題になるのが、符号ビットが立っている時の右シフト演算です。見逃されがちなポイントは、

• 型によって挙動(算術シフトか論理シフトか)がかわることがある
• C言語の規格として、算術シフトか論理シフトかは不定
• Nbitの算術シフトと2のN乗での除算は等価ではない

といったところにあります。
算術シフト(shift arithmetic)と論理シフト(shift logical:又は0充填シフト)という言葉をご存知ない方のためにちょっと説明を書いておくと、シフトによって空いたビット部分を符号ビットを同じもので詰めるのが算術シフト、0で詰めるのが論理シフトです。そのため、それぞれ、符号充填シフト、0充填シフトと呼ばれることもあります。詳しくは、Wikipedia(ビット演算)等を参照してください。

■型によって挙動がかわることがある

具体的な例をあげて説明します。次のコードを実行するとどうなるでしょうか。

#include <stdio.h>
int
main()
{
  long sval = 0xffffffff;
  unsigned long uval = 0xffffffff;

  sval >>= 8;
  uval >>= 8;

  printf("%#010x %#010x\n", (unsigned int)sval, (unsigned int)uval);

  return 0;
}

「0x00ffffff 0x00ffffff」という結果を予想される方もいるでしょう。しかし、実際gccでこのソースをコンパイルして実行すると、結果は「0xffffffff 0x00ffffff」となります。同じビットパターンを8bit右シフトしただけなのですが、型が符号付整数(signed)か符号なし整数(unsigned)かによって結果が異なっています。実は、gccではsignedなら算術シフト、unsignedなら論理シフトとなる実装になっているのです。実際、上記コードをコンパイルしたものをobjdumpで逆アセンブルした結果も乗せておきます。

  sval >>= 4;
 80483a6:       8d 45 f8                lea    0xfffffff8(%ebp),%eax
 80483a9:       c1 38 04                sarl   $0x4,(%eax)
  uval >>= 4;
 80483ac:       8d 45 fc                lea    0xfffffffc(%ebp),%eax
 80483af:       c1 28 04                shrl   $0x4,(%eax)

signedの場合は算術右シフト(sarl)命令、unsignedの場合は、論理右シフト命令(shrl)になっているのが確認できます。

このような実装のため、何気なく論理シフトを期待して右シフト処理を行っていると、たまたま変数の型がsignedの場合、思わぬバグの原因になることがあります。

■C言語の規格として、算術シフトか論理シフトかは不定

先程の例は、gccでコンパイルした時の話でした。なぜ、わざわざコンパイラを明記したかというと、先ほどの挙動(signedなら算術シフト、unsignedなら論理シフト)は、gccの仕様であって、C言語の仕様ではないのです。残念なことに、C言語の規格としては、右シフト時に算術シフトになるか論理シフトになるかは規定していません。つまり、処理系依存の動作になっています。よって、gccでコンパイルしている限りは、先程の挙動は保障されますが、他の処理系(例えば、全て論理シフトになっている処理系）との互換性は保障されません。大抵の処理系ではgccと同じような実装になっているため、C言語の解説サイトでも、C言語の仕様として書かれているのを見かけることがあります。しかし、保障はないので移植性が必要な場合は注意する必要があります。ちなみに、VC++も、gccと同じ実装です。

使用している処理系の右シフト動作がgccやVC++の動作に依存している場合、次のようなstatic_assertマクロでチェックを入れておくことができます。

#define STATIC_ASSERT(expr) { \
    char __STATIC_ASSERTION[(expr) ? 1 : -1]; \
    (void)__STATIC_ASSERTION; \
  }

/* 符号付き整数の右シフトが算術シフトかどうか */
#define SHIFT_LEFT_SINGNED_USES_SAL \
  (((signed int)0xffffffff >> 1) == 0xffffffff)

/* 符号無し整数の右シフトが論理シフトかどうか */
#define SHIFT_LEFT_UNSIGNED_USES_SHL \
  (((unsigned int)0xffffffff >> 1) == 0x7fffffff)

ソースのどこかで、

STATIC_ASSERT(SHIFT_LEFT_SINGNED_USES_SAL)

のように書いておけば、処理系の動作が期待値と異なる場合にコンパイルエラーになります。
勿論最初から依存しないように書けばいいのですが、条件分岐等を無駄に入れたくない場合には、処理系依存を承知の上でコードを書いて、上記のようなチェックコードを埋めておくというのもひとつの手です。

ちなみに、JavaではCにおける>>演算子に加えて>>>演算子が追加されているので、問題は緩和されていますね。

■Nbitの算術シフトと2のN乗での除算は等価ではない

では、gccとVC++は、型によって算術シフトと論理シフトを使い分けているのでしょうか。何もそんなややこしい仕様にしなくてもいいのにと思われる方もいるでしょう。
signedが算術シフトになっている理由とは、その名が示しているように、右シフト演算を整数演算(除算相当)になるようにするためです。具体的には、負数が2の補数で現れている場合、負数に右論理シフトを行うと、値の符号が変化してしまいますが、算術シフトにするとつじつまがあいます。右シフトが2の累乗での除算(例. x >> 1 == x / 2)、左シフトが2の累乗倍(例. x << 1 == x * 2)というルールが負数にも「ほぼ」当てはまるようになります。
ここで、「ほぼ」と書いたのがポイントで、実際は除算の方は「x >> 1 == x / 2」とはいかないことがあります。
C99以前のC言語の場合、負数の整数除算(/演算)は、切捨てになるか切り上げになるかが処理系依存でした。C99では、正負にかかわらず切り捨て(負数であれば、0方向への切り上げ)という規定が入りました。これによって、整数除算に関する移植性の問題はなくなりました。
2の補数で表現された負数の算術右シフトは、切り下げ(-1.5なら-2)です。よって、C99に従った整数除算と、算術右シフトは、切り上げ/切捨てが異なってしまいます。具体的は、「-3 / 2 == -1」「-3 >> 1 == -2」となります。C99以前のCの場合、整数除算の方が処理系依存ですので、一致することもあるかもしれないし、一致しないこともあるかもしれません。(私自身も「ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか」を読んでいて、初めて認識しました :-P)

何かと落とし穴の多い右シフト。使うときは十分注意しましょう。

（追記)
最初この記事を書いた時には、C99以前のC言語では負数の整数除算の扱いが不定ということを知りませんでした(konumaさんに指摘いただきました)。記事を書く前に、gccで動作＆アセンブラ確認もしたのですが、それでは処理系依存か否かという点はわかるはずもないですね。今回の教訓です。一度、こういった処理系依存の話についてもまとめてみたいと思います。

【関連記事】
・コンパイル時の静的チェック (STATIC_ASSERT)
・charの落とし穴 - 暗黙の型変換と符号拡張

【関連リンク】
・ビット演算 - Wikipedia
・シフト演算子 (Microsoft)
・シフト演算子 (二流プログラマの三流な日常)
・プログラミング言語Cの新機能 (C99に関する詳しい解説)

【関連書籍】
・ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか Jr,ヘンリー.S.ウォーレン
・Cプログラミングの落とし穴 A.コーニグ
・GCC GNU C Compiler―Manual & Reference 遠藤 俊徳
・プログラミング言語C ANSI規格準拠 B.W.カーニハン D.M.リッチー