難読 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 で得られます。