悪魔召喚

プログラミングパズルを見掛けた。

●◆■▲★×4＝★▲■◆●
同じ数字がひとつ入って、それぞれ同じ記号は同じ数字が入る。
●、◆、■、▲、★に適切な数字を求めよ。

http://d.hatena.ne.jp/doloopwhile/20100817/1282047776

C で解いてみた。

#include <stdio.h>

int rev(int x) {
  int s;
  for(s=0; x; x/=10) s=s*10+x%10;
  return s;
}

int main(void) {
  int i;
  for(i=10000; i<100000; i++)
    if(i*4==rev(i))
      printf("%d\n", i);
  return 0;
}

解として 21978 が表示される。 21978×4 は 87912 なので、正解になっていることがわかる。
では、このプログラムが正しいと言えるだろうか。
C の規格を完全に満たしたコンパイラでコンパイルしても期待通りの動作をしない場合があり得る。 問題は int のサイズだ。 C では int (や他の型) のサイズにいくらかの制約はあるものの、何ビットとは決められていないのである。 現在では int は 32 ビットのことが多く、上のコードでもそれを想定しているけども、これが 16 ビットでも C コンパイラとしては規格違反ではない。 そして 16 ビットの場合に表現可能な最大の数値は 32767 であるので、 5 桁の数を全て表現することは出来ず、オーバーフローを起こす。 C ではオーバーフローした場合にどうなるか未定義なので何が起こるかわからない。
問題が起こるケースを体験してみたければ、「LSI C-86 試食版」という無料で入手できるコンパイラがあるので、それで上述のコードをコンパイルしてみると良い。 int がオーバーフローすると -32767 になって永遠に 100000 を越えないので無限ループに突入することがわかる。 x86 系 CPU の加算命令の挙動そのままなので、それを知っていれば納得できる挙動なのだが、言語としての取り決めに基くものではない。 (他の環境ではエラーとして停止するかもしれないし、ハードディスクをフォーマットするかもしれないし、鼻から悪魔が出てくるかもしれない。)
更にやっかいなことのひとつが、こういった環境に特有の挙動を利用したコードが存在することで、しかも利用しないとやりたいことが書けない場合があるということだ。 初心者にとっての C の難しさの多くは型だとかポインタなんかではなく、言語以外のなんだかんだの事情の部分なんじゃないかと思っている。
Document ID: b9f4cc91dc0e11d68870f23969649431