如何高效将两个uint32_t值交错为单个uint64_t（Z阶曲线场景）

当然有，而且实现所需的CPU指令远少于100条，主流方案分两种：通用分治法（兼容所有CPU平台）和专用指令集优化法（依赖现代CPU指令集，效率更高）。

通用分治法（无平台依赖） #

核心思路是通过分阶段的位扩展与掩码操作，逐步将X、Y的比特位插入到目标位置，最终合并得到交错结果。整个过程仅需十几条位操作指令：

#include <stdint.h>

uint64_t interleave(uint32_t x, uint32_t y) {
    uint64_t z = (uint64_t)x << 32;
    // 分阶段扩展X的比特位，每一步在现有比特间插入空位置
    z = (z | (z << 16)) & 0x00FF00FF00FF00FFULL;
    z = (z | (z << 8)) & 0x0F0F0F0F0F0F0F0FULL;
    z = (z | (z << 4)) & 0x3333333333333333ULL;
    z = (z | (z << 2)) & 0x5555555555555555ULL;

    // 用同样方式扩展Y的比特位，再左移一位合并到Z的偶数位
    uint64_t y_expanded = (uint64_t)y << 32;
    y_expanded = (y_expanded | (y_expanded << 16)) & 0x00FF00FF00FF00FFULL;
    y_expanded = (y_expanded | (y_expanded << 8)) & 0x0F0F0F0F0F0F0F0FULL;
    y_expanded = (y_expanded | (y_expanded << 4)) & 0x3333333333333333ULL;
    y_expanded = (y_expanded | (y_expanded << 2)) & 0x5555555555555555ULL;

    z |= y_expanded << 1;
    return z;
}

原理说明 #

每一轮移位+掩码操作都会将当前比特的间隔翻倍：

• 第一次操作后，X的每8位之间插入8个空比特；
• 逐步缩小间隔，最终X的每个比特占据64位中的奇数位置（第1、3、5...位），Y扩展后左移一位占据偶数位置（第2、4、6...位），按位或后就得到xyxyxy...的交错结果。

专用指令集优化法（现代CPU） #

如果目标平台支持专用位操作指令，效率会更高，仅需2-3条CPU指令即可完成：

x86平台（支持BMI2指令集） #

利用PDEP（比特扩展）指令，直接将X、Y的比特映射到目标掩码位置：

#include <stdint.h>
#include <immintrin.h>

uint64_t interleave_bmi2(uint32_t x, uint32_t y) {
    // 0x5555555555555555 是二进制 0101... 掩码，对应奇数位
    // 0xAAAAAAAAAAAAAAAA 是二进制 1010... 掩码，对应偶数位
    return _pdep_u64(x, 0x5555555555555555ULL) | _pdep_u64(y, 0xAAAAAAAAAAAAAAAAULL);
}

ARM64平台（支持Zip指令） #

可使用zip1指令直接完成比特交错操作：

// 输入：w0 = X（32位），w1 = Y（32位）；输出：x0 = Z（64位）
mov     x0, x0          // 将X扩展为64位
mov     x1, x1          // 将Y扩展为64位
zip1    x0, x0, x1      // 交错X和Y的比特位，得到xyxy...顺序的64位结果

总结 #

两种方案的指令数都远低于100条：通用分治法约15条指令，专用指令集优化法仅2-3条指令，完全满足你的需求。

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