Bitwise Interleaving and Morton Code Explained

Bitwise interleaving, commonly known as generating a Morton code or Z-order curve, is a computational technique used to map multidimensional coordinates into a single one-dimensional index. By alternating the binary bits of coordinate values, this operation projects multi-axis data into a linear sequence while preserving spatial locality. This article explains how bitwise interleaving functions at the binary level, why it forms a Z-shaped spatial curve, and how it is used to efficiently organize and index multidimensional data.

What is Bitwise Interleaving?

Bitwise interleaving takes two or more binary numbers and merges them into a single binary number by alternating their bits. Invented by Guy Macdonald Morton in 1966, this process generates a “Morton code.”

When plotted in a multi-dimensional Cartesian grid, connecting sequential Morton codes forms a continuous fractal space-filling curve resembling repeating ‘Z’ patterns, which is why it is also known as the Z-order curve.

How It Works in the Binary System

To understand the operation, consider a two-dimensional coordinate system with two integer inputs, \(X\) and \(Y\):

1. Convert both coordinate values into their fixed-width binary representations.
2. Select bits sequentially, alternating between the coordinates from the most significant bit (MSB) to the least significant bit (LSB).

Concrete Example:

Suppose we want to encode the 2D point \((X = 5, Y = 3)\):

• Binary of X (5): 1 0 1 (Bits: \(x_2=1, x_1=0, x_0=1\))
• Binary of Y (3): 0 1 1 (Bits: \(y_2=0, y_1=1, y_0=1\))

To interleave them, pair each bit in the order \((y_n, x_n)\):

• Bit 2 (MSB): \(y_2 = 0\), \(x_2 = 1 \rightarrow \mathbf{01}\)
• Bit 1: \(y_1 = 1\), \(x_1 = 0 \rightarrow \mathbf{10}\)
• Bit 0 (LSB): \(y_0 = 1\), \(x_0 = 1 \rightarrow \mathbf{11}\)

Combining these pairs produces the interleaved Morton code: \[\text{Binary: } \mathbf{011011}_2\] \[\text{Decimal: } 27\]

For three dimensions \((X, Y, Z)\), the interleaving pattern simply alternates across three bits at a time \((z_n, y_n, x_n)\), and extends similarly to higher dimensions.

How It Organizes Multidimensional Data

In computer architecture, memory and storage systems are strictly linear (1D). Organizing multi-axis data (like 2D images, 3D voxel models, or geographical coordinates) presents a challenge: traditional row-major or column-major layouts keep points that are close along one axis near each other in memory, but points close along another axis end up far apart.

Bitwise interleaving solves this by providing key structural advantages:

• Preserving Spatial Locality: Points that are close to each other in 2D or 3D space generally have similar high-order bits. Consequently, their Morton codes remain close in the linear sequence, maximizing CPU cache efficiency.
• Hierarchical Decomposition: Each pair (or triplet) of bits in a Morton code corresponds to a specific quadrant in a 2D quadtree or octant in a 3D octree. This makes Morton codes equivalent to implicit tree paths.
• Efficient Range Queries: Bounding-box and nearest-neighbor searches can be executed quickly using simple bitwise masking and binary searches (such as with B-trees) rather than scanning multi-dimensional arrays.

Practical Applications

Because bitwise interleaving converts complex multidimensional relationships into standard integers, it is widely implemented in:

• Geographic Information Systems (GIS): Indexing latitude and longitude coordinates in spatial databases.
• Computer Graphics and GPUs: Texture mapping and bounding volume hierarchies (BVH) for ray tracing.
• Scientific Computing: N-body simulations and Barnes-Hut algorithms to cluster nearby particles efficiently.