Weaving Two Bitstreams Into One Address

Warp threads run vertical, weft horizontal. Where they cross, you get a coordinate. If you want to store a 2D grid in memory efficiently—pixels, tiles, spatial data—you face the same problem: how do you map (x, y) to a single address that keeps nearby points close together?

Bit interleaving solves this by threading the bits of x and y together, alternating like weft through warp. Take x = 5 (binary 101) and y = 3 (binary 011). Interleave them: y₂x₂y₁x₁y₀x₀ becomes 001111 = 15. That’s your Morton code, your Z-order index.

The pattern traces a recursive Z through space. Quadrants at every scale stay clustered. Graphics hardware in the ’80s used this for texture addressing—cache locality improved because a 2×2 block of pixels landed in adjacent memory. Spatial databases still use it.

def morton(x, y)
  result = 0
  8.times do |i|
    result |= ((x & (1 << i)) << i) | ((y & (1 << i)) << (i + 1))
  end
  result
end

puts morton(5, 3)  # 15
puts morton(127, 255)  # 261887

#include <stdio.h>
#include <stdint.h>

uint32_t morton(uint16_t x, uint16_t y) {
    uint32_t result = 0;
    for (int i = 0; i < 16; i++) {
        result |= ((x & (1 << i)) << i) | ((y & (1 << i)) << (i + 1));
    }
    return result;
}

int main(void) {
    printf("%u\n", morton(5, 3));        // 15
    printf("%u\n", morton(127, 255));   // 261887
}

The Z-order curve visits every cell exactly once, neighbours stay near, and you compress two dimensions into one without losing spatial relationships. It’s a weave pattern written in binary.