Namaran

Code daily. Without assist.

2026-11-16

morton.c

#include <stdio.h>

static unsigned morton(unsigned x, unsigned y) {
    unsigned z = 0;
    for (unsigned i = 0; i < 4; i++) {
        z |= ((x >> i) & 1u) << (2 * i);
        z |= ((y >> i) & 1u) << (2 * i + 1);
    }
    return z;
}

int main(void) {
    printf("%u %u %u\n", morton(1, 0), morton(0, 1), morton(2, 3));
}

これは何を出力するでしょうか?

Answer

Output

1 2 14

morton は、x の i ビット目を z の 2 * i ビット目へ、y の i ビット目を 2 * i + 1 ビット目へ置きます。z のビットは下から x、y、x、y と交互に並び、x は偶数番目、y は奇数番目に入ります。

morton(1, 0) では x の0ビット目だけが立っているので、z の0ビット目が立って 1 です。morton(0, 1) では y の0ビット目が z の1ビット目に入り、2 です。morton(2, 3) は、x が2進で 10、y が 11 です。i = 0 では y のビットだけが1ビット目に入って 2、i = 1 では x のビットが2ビット目に、y のビットが3ビット目に入って 4 + 8 です。合わせて 14(2進で 1110)になります。

y を偶数番目に置くと読み違えると、1 と 2 が入れ替わって 2 1 13 になります。どちらを偶数番目に置くかは決めごとですが、このコードでは 2 * i に入るのが x です。0から3までの (x, y) をこの値の順に並べると (0,0)、(1,0)、(0,1)、(1,1) となり、2×2のマスを「Z」の字を書く順に回ります。