# 非再帰で作るヒルベルト曲線


for 文でヒルベルト曲線状にアクセスしたいです。しかも、次の位置への移動をできるだけ高速に行いたいです。どうすれば良いでしょうか？

### 解

- 矢印の向き (縦 or 横) と
- 行/列 番号が増えるか (+1 or -1)

に分けて考えます。増えている矢印には赤の色を付けてあります。

矢印についている番号を `i` として、`i` の 4 進展開に注目すると、以下のことがわかります。

- 矢印の向き (0: 縦, 1: 横)
- `i` が 4 で割り切れる限り 4 で割り続ける。1 回割るごとに答えが反転する。
- その後、`i` を 2 進展開し、2 の位以外の popcount を求める。これ mod 2 が答えである。
- `((popcount(i >> (countr_zero(i) & ~1) & ~2) ^ countr_zero(i) >> 1) & 1`
- index が増えるか (0: 増える, 1: 減る)
- `i` の 4 進展開に含まれる 3 の個数 mod 2 が答え。
- `popcount((i & i >> 1) & 0x55555555) & 1`