如何用‘直观法’对3D Morton码进行解交错（逆莫顿化）？

我已经用直观位交错法实现了3D坐标转Morton码的函数xyz2w，代码运行正常，如下：

#include <limits.h> // 需要CHAR_BIT的定义

unsigned long xyz2w(unsigned int x, unsigned int y, unsigned int z)
{
    unsigned long w=0;

    for (int i = 0; i < sizeof(x) * CHAR_BIT; i++)
    {
        w |= (x & 1U << i) << i | (y & 1U << i) << (i + 1) | (z & 1U << i) << (i + 2);
    }

    return w;
}

现在需要实现反向操作：从Morton码中提取出对应的三维坐标(x, y, z)。我不需要高性能的位运算技巧实现，只需要和xyz2w风格一致的直观循环实现，方便理解对位操作的逻辑。

直观逆向实现代码 #

#include <limits.h>

void w2xyz(unsigned long w, unsigned int *x, unsigned int *y, unsigned int *z)
{
    // 先初始化坐标为0
    *x = 0;
    *y = 0;
    *z = 0;

    // 遍历原坐标的每一位（和xyz2w的循环次数一致）
    for (int i = 0; i < sizeof(unsigned int) * CHAR_BIT; i++)
    {
        // 提取Morton码中对应x的位：原x的第i位在w的第2*i位
        if (w & (1UL << (2 * i)))
        {
            *x |= 1U << i;
        }
        // 提取Morton码中对应y的位：原y的第i位在w的第2*i+1位
        if (w & (1UL << (2 * i + 1)))
        {
            *y |= 1U << i;
        }
        // 提取Morton码中对应z的位：原z的第i位在w的第2*i+2位
        if (w & (1UL << (2 * i + 2)))
        {
            *z |= 1U << i;
        }
    }
}

代码逻辑说明 #

• 和正向函数xyz2w的循环逻辑完全对应：正向是把x/y/z的每一位分别放到Morton码的2i/2i+1/2i+2位置；逆向就是反过来，从这些位置把位取出来，放回x/y/z的第i位。
• 循环次数和原坐标的位数一致（sizeof(unsigned int)*CHAR_BIT，通常是32次），确保每一位都被处理到。
• 每次循环中：
  1. 检查Morton码的2*i位是否为1，如果是，就把x的第i位设为1
  2. 检查Morton码的2*i+1位是否为1，如果是，就把y的第i位设为1
  3. 检查Morton码的2*i+2位是否为1，如果是，就把z的第i位设为1

内容的提问来源于stack exchange，提问作者Unemployed Goose