コードを短くするのって楽しいですよね？(8)

続、神の領域。

前回のコードをおさらいしておこう。

main(d){for(d=getchar()&1?227275:21;d-1;d/=2)puts(d&1?"yes":"no");}

どう見ても、このd-1とd/=2が冗長だ。d-1の部分がd/=2と書ければ良いのだが、そのためにはYesとNoと“番人”との3状態が必要になる。最後のテストケースの答えが必ずYesかNoならば、番人が不要になって2状態の保持だけで済むのだが、不運だとしか言いようがない。

そこで3状態を保持することを考える。これには、4進数でもいいのだが、4進数は1桁が2bitである。17のテストケースを表現するには17*2=34bit必要になる。これはintで通例、表現できる範囲を超えている。

そこで3進数を用いる。これがひとつ目のhackである。

main(d){for(d=getchar()&1?xxxxxxxxx:xx;d/=3;)puts(d%3%2?"yes":"no");}

終了判定は短くなったが、3進数17桁で表現できる最大値は=129,140,162 で9桁もある。また、今度はd%3%2が冗長だ。そもそも、9桁の数字をいかに短く表現できるかという問題もある。

ここで、二つ目のhackが必要になる。gcc拡張(?)の、文字リテラルである。'abcd'のように書けば('a'<<24)+('b'<<16)+('c'<<8)+'d'の意味になる。これを使えば32bit幅の定数であっても6文字で表現できる。ただし、ブラウザからフォームに貼り付ける制約上、あまり特殊な文字コードは送信できない。

三つ目のhackは、「d%3%2」の部分をもっと短く書けないかについてだ。この部分、実は、「d&1」と書ける。一体、3進数で表現してある数字のbit0が何を意味するのだろうか？(つづく)