在一个字中间隔位的快速方法是什么？

Question

我在64位寄存器的低位部分有一个32位值；顶部部分是 0。让我们X用信息来表示一个位，并用从 LSB 到 MSB 列出的位来表示，如下所示：

X X X  ...  X 0 0 0 0 ... 0

现在，我想用信息“间隔”这些位，这样我就有了

X 0 X 0 X 0 ... X 0

（或者如果你想把 0 放在前面，那么

0 X 0 X 0 X 0 ... X

也很好。）

有什么快速的方法可以做到这一点？

与多 CPU 架构相关的答案会很好，但特定于 Intel x86_64 和/或 nVIDIA Pascal SM 的答案将是最相关的。

Answer 1

这被称为莫顿数，它是并行扩展的一个特例，而并行扩展又是以下问题中压缩右的逆过程。

\n

\n
• 将 32 0/1 值打包到单个 32 位变量的位中的最快方法是什么？
\n
• 将屏蔽位移至 lsb
\n

\n

一种通用的解决方案可能是

\n\n

uint64_t bit_expand(uint64_t x)\n{\n    // Input:  00000000ABCDEFGH, each character is a nibble\n    x = ((x & 0xFFFF0000) << 32) | ((x & 0x0000FFFF) << 16);\n    // Result: ABCD0000EFGH0000\n    x = (x & 0xFF000000FF000000) | ((x & 0x00FF000000FF0000) >> 8);\n    // Result: AB00CD00EF00GH00\n    x = (x & 0xF000F000F000F000) | ((x & 0x0F000F000F000F00) >> 4);\n    // Result: A0B0C0D0E0F0G0H0. Each byte: abcd0000\n    x = (x & 0xC0C0C0C0C0C0C0C0) | ((x & 0x3030303030303030) >> 2);\n    // Result:                   Each byte: ab00cd00\n    x = (x & 0x8888888888888888) | ((x & 0x4444444444444444) >> 1);\n    // Result:                   Each byte: a0b0c0d0\n    return x;\n}\n

\n

然而，常量生成在 RISC 架构上可能效率低下，因为 64 位立即数无法像 x86 那样存储在单个指令中。即使在 x86 上，输出程序集也相当长。这是Bit Twiddling Hacks中描述的另一种可能的实现

\n

static const unsigned int B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF};\nstatic const unsigned int S[] = {1, 2, 4, 8};\n\nunsigned int x; // Interleave lower 16 bits of x and y, so the bits of x\nunsigned int y; // are in the even positions and bits from y in the odd;\nunsigned int z; // z gets the resulting 32-bit Morton Number.  \n                // x and y must initially be less than 65536.\n\nx = (x | (x << S[3])) & B[3];\nx = (x | (x << S[2])) & B[2];\nx = (x | (x << S[1])) & B[1];\nx = (x | (x << S[0])) & B[0];\n\ny = (y | (y << S[3])) & B[3];\ny = (y | (y << S[2])) & B[2];\ny = (y | (y << S[1])) & B[1];\ny = (y | (y << S[0])) & B[0];\n\nz = x | (y << 1);\n

\n

一个查找表也可以使用

\n

#define EXPAND4(a) ((((a) & 0x8) << 4) | (((a) & 0x4) << 2) \\\n                  | (((a) & 0x2) << 1) | (((a) & 0x1)))\n\nconst uint8_t LUT[16] = {\n    EXPAND4( 0), EXPAND4( 1), EXPAND4( 2), EXPAND4( 3),\n    EXPAND4( 4), EXPAND4( 5), EXPAND4( 6), EXPAND4( 7),\n    EXPAND4( 8), EXPAND4( 9), EXPAND4(10), EXPAND4(11),\n    EXPAND4(12), EXPAND4(13), EXPAND4(14), EXPAND4(15)\n};\n\noutput = ((uint64_t)LUT[(x >> 28) & 0xF] << 56) | ((uint64_t)LUT[(x >> 24) & 0xF] << 48)\n       | ((uint64_t)LUT[(x >> 20) & 0xF] << 40) | ((uint64_t)LUT[(x >> 16) & 0xF] << 32)\n       | ((uint64_t)LUT[(x >> 12) & 0xF] << 24) | ((uint64_t)LUT[(x >>  8) & 0xF] << 16)\n       | ((uint64_t)LUT[(x >>  4) & 0xF] <<  8) | ((uint64_t)LUT[(x >>  0) & 0xF] <<  0);\n

\n

如有必要，可以增加查找表的大小

\n\n

在具有BMI2的 x86 上，有PDEP的硬件支持指令的硬件支持，可以通过以下内在函数访问

\n

output = _pdep_u64(x, 0xaaaaaaaaaaaaaaaaULL);\n

\n\n

另一种没有位存储/扩展指令但具有快速乘法器的架构解决方案

\n

uint64_t spaceOut8bits(uint8_t b)\n{\n    uint64_t MAGIC = 0x8040201008040201;\n    uint64_t MASK  = 0x8080808080808080;\n    uint64_t expand8bits = htobe64(((MAGIC*b) & MASK) >> 7);\n    uint64_t spacedOutBits = expand8bits*0x41041 & 0xAA000000AA000000;\n    return (spacedOutBits | (spacedOutBits << 24)) & 0xFFFF000000000000;\n}\n\nuint64_t spaceOut64bits(uint64_t x)\n{\n    return (spaceOut8bits(x >> 24) >>  0)\n         | (spaceOut8bits(x >> 16) >> 16)\n         | (spaceOut8bits(x >>  8) >> 32)\n         | (spaceOut8bits(x >>  0) >> 48);\n}\n

\n

它的工作方式是这样的

\n

\n
• 第一步将输入位从abcdefgha0000000 b0000000 c0000000 d0000000 e0000000 f0000000 g0000000 h0000000展开并存储在expand8bits
\n
• 然后，我们在下一步中通过乘法和屏蔽将这些间隔开的位移近。之后spacedOutBits将包含a0b0c0d0 00000000 00000000 00000000 e0f0g0h0 00000000 00000000 00000000。我们将结果中的两个字节合并在一起
\n

\n

使位更接近的幻数是这样计算的

\n

  a0000000b0000000c0000000d0000000e0000000f0000000g0000000h0000000\n\xc3\x97                                              1000001000001000001\n  \xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\n  a0000000b0000000c0000000d0000000e0000000f0000000g0000000h0000000\n  00b0000000c0000000d0000000e0000000f0000000g0000000h0000000\n+ 0000c0000000d0000000e0000000f0000000g0000000h0000000\n  000000d0000000e0000000f0000000g0000000h0000000\n  \xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\n  a0b0c0d0b0c0d0e0c0d0e0f0d0e0f0g0e0f0g0h0f0g0h000g0h00000h0000000\n& 1010101000000000000000000000000010101010000000000000000000000000\n  \xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\n  a0b0c0d0000000000000000000000000e0f0g0h0000000000000000000000000\n

\n

输出组件可以在这里看到。您可以更改编译器以查看它在各种体系结构上的完成情况

\n

关于Bit Twiddling Hacks还有一种替代方法页面

\n

z = ((x * 0x0101010101010101ULL & 0x8040201008040201ULL) * \n     0x0102040810204081ULL >> 49) & 0x5555 |\n    ((y * 0x0101010101010101ULL & 0x8040201008040201ULL) * \n     0x0102040810204081ULL >> 48) & 0xAAAA;\n

\n

更多解决方案可以在不使用 BMI2 的情况下便携式高效替代 PDEP？

\n

相关：如何对像素数据进行位条纹？

\n

正如您所看到的，如果没有位存储指令，操作将非常复杂。如果您不进行像这样的位条带化操作，那么最好使用 SIMD 并行执行

\n