ビット演算利用の FizzBuzz コードを読み解く


断捨離

こんなの↓

```
$ perl -E 'say +($_,Fizz,Buzz,FizzBuzz)[3&19142723>>2*$_%30] for 1..100'
$ ruby -e '(1..100).step{|x| puts [x,"Fizz","Buzz","FizzBuzz"][3&19142723>>2*x%30]}'
```


##### 前提

- FizzBuzz は当然出来るものとしての話。
- `perl` を元に記載するが、ビットの取扱部分とかは、他の言語も同様だろう。


## FizzBuzz の結果の特徴

コードを読み解く前に FizzBuzz の特徴、改めて書くまでも無い事だけど。

- 15 回毎の繰り返し
- 数字、Fizz, Buzz, FizzBuzz を 0,1,2,3 とフラグ化出来る


|-|-|-|-|-|-|-|
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|1|16|31|46|61|76|91|
|2|17|32|47|62|77|92|
|Fizz|Fizz|Fizz|Fizz|Fizz|Fizz|Fizz|
|4|19|34|49|64|79|94|
|Buzz|Buzz|Buzz|Buzz|Buzz|Buzz|Buzz|
|Fizz|Fizz|Fizz|Fizz|Fizz|Fizz|Fizz|
|7|22|37|52|67|82|97|
|8|23|38|53|68|83|98|
|Fizz|Fizz|Fizz|Fizz|Fizz|Fizz|Fizz|
|Buzz|Buzz|Buzz|Buzz|Buzz|Buzz|Buzz|
|11|26|41|56|71|86||
|Fizz|Fizz|Fizz|Fizz|Fizz|Fizz||
|13|28|43|58|73|88||
|14|29|44|59|74|89||
|FizzBuzz|FizzBuzz|FizzBuzz|FizzBuzz|FizzBuzz|FizzBuzz||


4進数のフラグ

```
001021001201003
```
の繰り返しだと解釈出来る。

## コードを読み解く

`3&810092048>>2*($_-1)%30` の方かとも思ったけど、説明しやすい方で。


### 4進数のフラグから、文字列への変換

リストのスライスを利用して、 `($_,'Fizz','Buzz','FizzBuzz')` から `[0..3]` で選択してる[^1]。

[^1]: コードゴルフなので、問題のコードではクォートは省略


### 2進数変換

普通に、4進数の羅列だと、

```
$ perl -le 'print +( split //, q{001021001201003})[14]'
3
```
などとして切り出す事が出来るが、冗長となる。で、ここではビットシフトと論理積を利用する。

上記の4進数を、2桁2進数にし、連結したものを用意。

```pl:A
$ perl -le 'printf "%02b", $_ for split//, "001021001201003" ; print '
000001001001000001100001000011 
# 2桁毎に空白を入れたら以下の様に
# 00 00 01 00 10 01 00 00 01 10 00 01 00 00 11
```



#### 10進数で表示してみると

```
$ perl -le 'print 0b000001001001000001100001000011'
19142723
```

### 切り出し

前述の通り、ビットシフトで A の（空白抜きの）結果をシフトし、

```pl:例えば、数字の5のフラグは？
$ perl -le 'printf "%010b\n", 0b000001001001000001100001000011>>2*(15-5)' 
0000010010
# 2桁毎に空白を入れたら以下の様に
# 00 00 01 00 10
```

- フラグは30桁の左から並ぶため、左から5番目のフラグを1桁目に持ってくる（10桁に切り詰める）為には、
15 からの差分を 2 で掛けた分だけシフトする必要がある。


で、論理積で、フラグのみを切り出す。

```pl:例えば、数字の5のフラグは？
$ perl -le 'printf "%02b\n", 0b11&0b0000010010'
10
```

- 二進数11の論理積を取ると、末尾2桁を切り取る事が出来る。
	- 双方1なら1、片方でも0なら0を返すから。
- 二進数10は2。つまり、上の無名配列では、3番目の 'Buzz' を示す index


### 後は、シフトを上手く制御する

##### 確かめ算
```pl:B
$ perl -e 'my @a = 1 .. 15 ; my @b = reverse @a ; shift @b ; push @b, 0 ;' \
       -e 'print join "\t", $a[$_], $b[$_], $a[$_] % 15 and printf "\t%02b\n", 0b11&0b000001001001000001100001000011>>2*$b[$_] for 0 .. 14'
1       14      1       00
2       13      2       00
3       12      3       01
4       11      4       00
5       10      5       10
6       9       6       01
7       8       7       00
8       7       8       00
9       6       9       01
10      5       10      10
11      4       11      00
12      3       12      01
13      2       13      00
14      1       14      00
15      0       0       11
```

左から、数値、シフトしたい数（の1/2）、数値の剰余 `%15`、欲しいフラグ

#### 本来なら、

```
$ perl -e 'printf "$_\t%02b\n", 0b11&0b000001001001000001100001000011>>2*(15-($_%15||15)) for 1..100'
1       00
2       00
3       01
4       00
5       10
6       01
7       00
8       00
9       01
10      10
11      00
12      01
13      00
14      00
15      11
16      00
17      00
（略）
```


などとしてフラグを取り出す所。

`(15-($_%15||15))` は、

- `$_%15` => 数値の剰余を得て
- `||15`  => 剰余が 0 の場合のみ 15 をセットして
- 15 から引く

事で、シフトしたい数を算出。



#### 問題のコードでは、

剰余 1 から 14 と、 14 から 1 で、フラグ自体は同じである事を利用して、`(15-($_%15||15))` を、`($_%15)` に置き換えてる

```
$ perl -e 'printf "$_\t%d\t%d\n", (15-($_%15||15)), ($_%15) for 1..100'
1       14      1
2       13      2
3       12      3
4       11      4
5       10      5
6       9       6
7       8       7
8       7       8
9       6       9
10      5       10
11      4       11
12      3       12
13      2       13
14      1       14
15      0       0
16      14      1
17      13      2
（略）
```

### 以上の結果、

```
$ perl -le 'print+($_,Fizz,Buzz,FizzBuzz)[0b11&0b000001001001000001100001000011>>2*($_%15)] for 1 .. 100'
```
が導き出され、`2*()` の括弧の省略と、`0b~~` の十進数表記にて、問題のコードとなる。あ、あと `use feature`。


## メモに残ってた他の FizzBuzz
つっても一個だけだけど。

```
$ perl -E 'say +(Fizz)[$_%3].(Buzz)[$_%5]||$_ for 1..100'
```