主页 / coding / 问题 / 77515753
Accepted
fadedbee
Asked: 2023-11-20 20:03:34 +0800 CST

如何将两个 uint32_t 值交错为一个 uint64_t？

  • 772

如果我有两个 32 位值 X 和 Y，如何有效地将它们的位按照 xyxyxyxy 的顺序交错为一个 64 位值 Z...（Z 是 Z 顺序曲线上的一个位置。）

我可以迭代 X 和 Y 中的每个位，同时设置 Z 中的位。这看起来效率很低。

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

c

3 个回答

  1. Best Answer

    此 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");
}
    • 2

  2. 无论如何，这是一个手动矢量化版本，它使用 SSE 内在函数同时对 x 和 y 进行位运算。然而，gcc 编译器对我来说太聪明了，它以某种方式更有效地优化了尼尔森的标量函数。

    不管怎样，这可行，但可能只对那些可能想要调整它以使用更宽的向量宽度来同时交错一对以上 uint32_ts 的人有用。

    uint64_t interleavesse2(uint32_t x0, uint32_t y0) {
  // Works but is almost 50% slower!! than scalar version when compiled with gcc -O3 -msse2
  // Materially faster than when scalar version compiled with gcc -O2 -msse2
  __m128i mask = _mm_setr_epi32(0xffff, 0xffff, 0xffff, 0xffff);
  __m128i z = _mm_setr_epi32(x0, 0, y0, 0);
  z = _mm_and_si128(_mm_or_si128(z, _mm_slli_epi64(z, 16)), mask);
  mask = _mm_setr_epi32(0xff00ff, 0xff00ff, 0xff00ff, 0xff00ff);
  z = _mm_and_si128(_mm_or_si128(z, _mm_slli_epi64(z, 8)), mask);
  mask = _mm_setr_epi32(0xf0f0f0f, 0xf0f0f0f, 0xf0f0f0f, 0xf0f0f0f);
  z = _mm_and_si128(_mm_or_si128(z, _mm_slli_epi64(z, 4)), mask);
  mask = _mm_setr_epi32(0x33333333, 0x33333333, 0x33333333, 0x33333333);
  z = _mm_and_si128(_mm_or_si128(z, _mm_slli_epi64(z, 2)), mask);
  mask = _mm_setr_epi32(0x55555555, 0x55555555, 0x55555555, 0x55555555);
  z = _mm_and_si128(_mm_or_si128(z, _mm_slli_epi64(z, 1)), mask);
  uint64_t res[2];
  memcpy(res, &z, 16);
  return res[0] | (res[1] << 1);
}
    • 0

  3. 你是否必须经常这样做，比如你有很多 X 与很多 Y 交错吗？如果没有，下面的内容仅供参考。

    如果是，则存在“正交”方法。假设您有 128 个 X 与 128 个 Y 交错。从 32 128 位向量开始，将 X[0] 的位放在 32 个向量的第 0 位中。将 X[1] 的位放入向量的第 1 位，依此类推。对另一组 32 128 位向量中的 Y 值执行相同的操作。这有效地将值中的位转置为一组向量中的位列。然后，交错它们只是在从两组向量重新构建 64 位值时交替索引 X 向量和 Y 向量的情况。

    诚然，仅对于交织而言，将整数转置为向量数组中的位列可能效率低下。但是，如果稍后要完成更多位操作，则可以减少大量工作来重新索引数组中的向量。一些 SIMD 单元（如 Altivec）具有可以帮助进行转置的向量指令。

    按位逻辑运算（例如 AND）仍然可以完成（一次 1 位，但一次 128 个不同的值），但没有速度优势。然而，在已经转置的表示中也没有缺点。如果处理是一系列位操作和按位操作，则位操作实际上是“自由的”，这就是可以节省时间的地方。

    • 0

相关问题