C++ 如何将两个uint32_t值交织成一个uint64_t

发布于11月20日

如果我有两个32位的值X和Y，我如何有效地将它们的位交织成一个64位的值Z，顺序为xyxyxyxy. (Z是Z阶曲线上的位置.)

我可以迭代X和Y中的每一位，在执行过程中设置Z中的位.这似乎效率不高.

有没有一种捷径可以将两个值中的位交错为一个大值，从而只需不到一百条CPU指令？

推荐答案

这个C++答案也适用于C:https://stackoverflow.com/a/39490836/11993121

答案概述了原则，但没有写出完整的解决方案.工作实现如下所示:

#include <stdint.h>

uint64_t interleave(uint32_t x0, uint32_t y0)
{
    static const uint64_t B[] = {0x0000FFFF0000FFFF, 0x00FF00FF00FF00FF, 0x0F0F0F0F0F0F0F0F, 0x3333333333333333, 0x5555555555555555};
    static const unsigned S[] = {16, 8, 4, 2, 1};

    uint64_t x = x0;
    uint64_t y = y0;

    for(unsigned i = 0; i < sizeof(B)/sizeof(B[0]); i++)
    {
        x = (x | (x << S[i])) & B[i];
        y = (y | (y << S[i])) & B[i];
    }
    return x | (y << 1);
}

测试示例:

#include <stdio.h>

void printBinary64(uint64_t x)
{
    uint64_t bit = ((uint64_t)1 << 63);
    for(unsigned i = 0; i < 64; i++)
    {
        printf("%c", (x&bit) ? '1' : '0');
        bit = bit >> 1;
    }
}

void printBinary32(uint32_t x)
{
    uint32_t bit = ((uint32_t)1 << 31);
    for(unsigned i = 0; i < 32; i++)
    {
        printf("%c ", (x&bit) ? '1' : '0');
        bit = bit >> 1;
    }
}

int main(void)
{
    uint32_t x = 0x01234567;
    uint32_t y = 0xFEDCBA98;
    printf(" ");
    printBinary32(x);
    printf("\n");
    printBinary32(y);
    printf("\n");
    printBinary64(interleave(x,y));
    printf("\n");
}