難読 FizzBuzz: N進カウンタ篇
LL魂にて、にしおくんの顔を見ていたら、無性に難読 FizzBuzzを超えてみたくなってしまったので、以前ベッドの中でちらっと思いついたアイデアを休み時間中に実装してみました。
FizzBuzz とは何か、については→ どうしてプログラマに・・・プログラムが書けないのか?
#!/bin/env perl my $bits = 0; for ( my $i = 1; $i < 100; $i++ ) { my $tmp = $bits & 0x1b; $tmp |= $tmp >> 1; $tmp |= $tmp >> 1; $bits <<= 1; $bits &= 0x1b; $bits |= (~$tmp) & 0x05; if ($bits == 0) { print "FizzBuzz\n"; } elsif (($bits & 0x03) == 0) { print "Fizz\n"; } elsif (($bits & 0x1c) == 0) { print "Buzz\n"; } else { print "$i\n"; } }
ソースコードから意味を追うのはかなりたいへんだと思いますが、原理は簡単です。
1周期+αの $bits の値を2進で出力すると:
00101 01110 11000 10001 00010 00100 01101 11010 10000 00001 00110 01100 11001 10010 00000 00101
これを見ると、最下位2bitが 00->01->10->00 を、その上3bitが 000->001->011->110->100->000 を繰り返していることが分かります。Q.E.D.
発想元は、フリップフロップの組み合わせで3進カウンタと5進カウンタを作る、というただそれだけです。実際、TTL で組む場合は、FFが5個と、NOR2個で構成でき、Fizz信号とBuzz信号を取り出すのにそれぞれNOR2個で済むかと思います。
論理回路はけっこう綺麗になりましたので、本当はプログラムのほうも論理演算をあと1〜2個は減らせると思っていたのですが、1時間仕事としては僕にはこのくらいが限界でした……。挑戦すればもう少し綺麗にかけるかもしれません。
Cで書けば、論理演算や代入の合間にシフトがおまけでできる ARM みたいな CPU では、それなりに少ないステップで実行できるはず。
某学科のCPU演習はこんなところでも役立つ、ということで(笑)
ちょっとだけ補足
いくらなんでも説明をはしょりすぎな気もしますので、ポイントだけ補足を。最下位ビットを b0 と呼ぶことにします。
1ステップで $bits に対して以下の操作を並行に行いたい。
b0 = b0 nor b1 b1 = b0 b2 = b3 nor b4 b3 = b2 b4 = b3
nor を計算している部分の肝が以下:
my $tmp = $bits & 0x1b; $tmp |= $tmp >> 1; $tmp |= $tmp >> 1;
下の2行により、$tmp は、b0 = b0 | b1 | b2 に、b2 = b2 | b3 | b4 にそれぞれなります。が、b2 はその前にマスクされており 0 であることが保障されていますので、結局 b0 = b0 | b1 に、b2 = b3 | b4 になります。この演算結果の b0 と b2 だけをマスクして、あとで $bits の同じ位置にセットしてます。
ちなみに、Fizz = b0 nor b1, Buzz = b2 nor b4 で得られます。