非再帰版マージソート (続き)
「あとで考える」と書いたまま放っておいたらコメントをしてくれた人がいたので、改めて考えてみたい。とりあえず、謎の数式$bits = ($i - 1) ^ $i、$w1 = $bits & (-$bits)について調べてみた。
| x | x^(x-1) | x&(-x) |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 3 | 2 |
| 3 | 1 | 1 |
| 4 | 7 | 4 |
| 5 | 1 | 1 |
| 6 | 3 | 2 |
| 7 | 1 | 1 |
| 8 | 15 | 8 |
| 9 | 1 | 1 |
| 10 | 3 | 2 |
| 11 | 1 | 1 |
| 12 | 7 | 4 |
| 13 | 1 | 1 |
| 14 | 3 | 2 |
| 15 | 1 | 1 |
| 16 | 31 | 16 |
| 17 | 1 | 1 |
| 18 | 3 | 2 |
| 19 | 1 | 1 |
| 20 | 7 | 4 |
| 21 | 1 | 1 |
| 22 | 3 | 2 |
| 23 | 1 | 1 |
| 24 | 15 | 8 |
| 25 | 1 | 1 |
| 26 | 3 | 2 |
| 27 | 1 | 1 |
| 28 | 7 | 4 |
| 29 | 1 | 1 |
| 30 | 3 | 2 |
| 31 | 1 | 1 |
左がy=(x)=x^(x-1)のグラフ、右がy=
(x)=x&(-x)のグラフ。
これをみるとどちらも似たような形をしている。x=のときそれぞれy=2x-1、y=xとなり、それ以外の時はy=f(x)=f(x mod M)、ただしMは
(n=1,2,3,...)のうちxを越えない最大の数。
逆写像を考えるともっと分かりやすいかもしれない。
(x)=1,
(x)=1: x=1,3,5,7,9,11,13,15,...
(x)=3,
(x)=2: x=2,6,10,14,18,...
(x)=7,
(x)=4: x=4,12,20,...
(x)=15,
(x)=8: x=8,24,...
なるほど。を先頭に等差
級数数列になっているのか。
じゃあこの数式がプログラム上でどういう役割を果たしているのか？ というのは次回までの課題ということで、今回はここまで。
