如何在C语言中高效实现Z-order曲线的z值转(x,y)坐标？

当然有快速的位操作方案实现Z-order z值到(x,y)坐标的转换，核心思路是利用位掩码和分治移位，把z值中分散的x、y位快速聚集起来，完全不用逐位循环，效率和坐标转z值的快速方法相当。

原理回顾 #

Z-order曲线的编码逻辑是把x和y的二进制位交叉排列得到z值：z的第0位对应x的第0位，第1位对应y的第0位，第2位对应x的第1位，第3位对应y的第1位，以此类推。反向解码时，只需要把z的**偶数位（0、2、4...）**提取出来组成x，**奇数位（1、3、5...）**提取出来组成y。

快速解码的C实现（32位整数） #

下面的代码用分治法逐步将分散的位聚集为连续的坐标值，所有操作都是固定次数的位运算，时间复杂度为O(1)：

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

// 从z值解码得到x坐标
uint32_t z_to_x(uint32_t z) {
    z &= 0x55555555;          // 保留z的偶数位（x的原始位）
    z = (z | (z >> 1)) & 0x33333333; // 每2位合并，得到x的每2位片段
    z = (z | (z >> 2)) & 0x0F0F0F0F; // 每4位合并
    z = (z | (z >> 4)) & 0x00FF00FF; // 每8位合并
    z = (z | (z >> 8)) & 0x0000FFFF; // 最终将所有x位聚集到低16位
    return z;
}

// 从z值解码得到y坐标
uint32_t z_to_y(uint32_t z) {
    z = (z >> 1) & 0x55555555; // 把z的奇数位移到偶数位位置，对齐x的处理逻辑
    z = (z | (z >> 1)) & 0x33333333;
    z = (z | (z >> 2)) & 0x0F0F0F0F;
    z = (z | (z >> 4)) & 0x00FF00FF;
    z = (z | (z >> 8)) & 0x0000FFFF;
    return z;
}

// 测试示例
int main() {
    // 测试：z=5（二进制101）对应x=1（01）、y=1（01）
    uint32_t z = 5;
    uint32_t x = z_to_x(z);
    uint32_t y = z_to_y(z);
    printf("z=0x%x → x=0x%x, y=0x%x\n", z, x, y);
    return 0;
}

代码解释 #

1. 掩码筛选：用0x55555555（二进制0101...）保留目标位（x对应偶数位，y先把奇数位移到偶数位再处理）。
2. 分治聚集：通过多次移位和掩码操作，逐步把分散的2位、4位、8位片段聚集到一起，最终得到连续的坐标二进制值。
3. 适配64位：如果需要处理64位z值，只需将掩码替换为0x5555555555555555、0x3333333333333333等，最后移位到低32位即可。

这种方法完全避免了循环，所有操作都是CPU原生支持的位运算，速度极快，和你提到的坐标转z值的快速实现性能匹配。

内容的提问来源于stack exchange，提问作者Francesco Urdih