有什么快速的方法可以在一个单词中空格？

Question

我在一个64位寄存器的下部有一个32位的值；顶部是0。让< code>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架构相关的答案会很好，但一些特定于英特尔x86_64和/或nVIDIA Pascal SM的答案会是最相关的。

Answer 1

这里有一种结合初始移位和选择性加法的替代方法：

#include <stdint.h>

uint64_t expand_32_64(uint64_t x) {
    x = ((x &       0xFFFF0000) << 16) | (x &       0x0000FFFF);
    x = ((x &   0xFF000000FF00) <<  8) | (x &   0x00FF000000FF);
    x = ((x & 0xF000F000F000F0) <<  4) | (x & 0x0F000F000F000F);
    x += x & 0x0808080808080808;
    x += x & 0x1414141414141414;
    x += x & 0x2A2A2A2A2A2A2A2A;
    return x + x;  /* remove the last addition for expand_32_63 */
}

Answer 2

这可能不是最有效或最优雅的解决方案，但它是最容易理解的 IMO：

for (int i = 31; i >=0; i--) {
    reg |= ((reg >> i) & 1) << 2*i;
    reg &= ~(1 << i)
}

这会将 00000000ABCDEFGH 转换为 0A0B0C0D0E0F0G0H（实际上，该示例是一个 16 位数字，您可以将 31 替换为 7。但你知道我的意思）如果你想要右边的零，A0B0C0D0E0F0G0H0，将 2*i 替换为 2*i 1。

Answer 3

这就是众所周知的莫顿数，它是并行扩展的一个特例，在下面的问题中，它反过来又是右压缩的逆运算

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

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

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

然而，常量生成在RISC体系结构上可能是低效的，因为64位立即数不能像在x86上那样存储在单个指令中。即使在x86上，输出程序集也很长。这里是另一个可能的实现，如比特扭曲黑客所描述的

static const unsigned int B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF};
static const unsigned int S[] = {1, 2, 4, 8};

unsigned int x; // Interleave lower 16 bits of x and y, so the bits of x
unsigned int y; // are in the even positions and bits from y in the odd;
unsigned int z; // z gets the resulting 32-bit Morton Number.  
                // x and y must initially be less than 65536.

x = (x | (x << S[3])) & B[3];
x = (x | (x << S[2])) & B[2];
x = (x | (x << S[1])) & B[1];
x = (x | (x << S[0])) & B[0];

y = (y | (y << S[3])) & B[3];
y = (y | (y << S[2])) & B[2];
y = (y | (y << S[1])) & B[1];
y = (y | (y << S[0])) & B[0];

z = x | (y << 1);

也可以使用查找表

#define EXPAND4(a) ((((a) & 0x8) << 4) | (((a) & 0x4) << 2) \
                  | (((a) & 0x2) << 1) | (((a) & 0x1)))

const uint8_t LUT[16] = {
    EXPAND4( 0), EXPAND4( 1), EXPAND4( 2), EXPAND4( 3),
    EXPAND4( 4), EXPAND4( 5), EXPAND4( 6), EXPAND4( 7),
    EXPAND4( 8), EXPAND4( 9), EXPAND4(10), EXPAND4(11),
    EXPAND4(12), EXPAND4(13), EXPAND4(14), EXPAND4(15)
};

output = ((uint64_t)LUT[(x >> 28) & 0xF] << 56) | ((uint64_t)LUT[(x >> 24) & 0xF] << 48)
       | ((uint64_t)LUT[(x >> 20) & 0xF] << 40) | ((uint64_t)LUT[(x >> 16) & 0xF] << 32)
       | ((uint64_t)LUT[(x >> 12) & 0xF] << 24) | ((uint64_t)LUT[(x >>  8) & 0xF] << 16)
       | ((uint64_t)LUT[(x >>  4) & 0xF] <<  8) | ((uint64_t)LUT[(x >>  0) & 0xF] <<  0);

如果需要，可以增加查找表的大小

在带有BMI2的x86上，有PDEP指令的硬件支持，可以通过以下内部

output = _pdep_u64(x, 0xaaaaaaaaaaaaaaaaULL);

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

uint64_t spaceOut8bits(uint8_t b)
{
    uint64_t MAGIC = 0x8040201008040201;
    uint64_t MASK  = 0x8080808080808080;
    uint64_t expand8bits = htobe64(((MAGIC*b) & MASK) >> 7);
    uint64_t spacedOutBits = expand8bits*0x41041 & 0xAA000000AA000000;
    return (spacedOutBits | (spacedOutBits << 24)) & 0xFFFF000000000000;
}

uint64_t spaceOut64bits(uint64_t x)
{
    return (spaceOut8bits(x >> 24) >>  0)
         | (spaceOut8bits(x >> 16) >> 16)
         | (spaceOut8bits(x >>  8) >> 32)
         | (spaceOut8bits(x >>  0) >> 48);
}

它的工作方式是这样的

• 第一步将输入位从 abcdefgh 扩展到 a0000000 b0000000 c0000000 d0000000 e0000000 f0000000 g0000000 h0000000 并存储在 expand8 位中
• 然后，我们在下一步中通过乘法和掩码将这些间隔的位移近在一起。之后，间隔OutBits将包含a0b0c0d0 000000000 000000000 00000000 e0f0g0h0 000000000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000我们将结果中的两个字节合并在一起

使比特更接近的神奇数字是这样计算的

  a0000000b0000000c0000000d0000000e0000000f0000000g0000000h0000000
×                                              1000001000001000001
  ────────────────────────────────────────────────────────────────
  a0000000b0000000c0000000d0000000e0000000f0000000g0000000h0000000
  00b0000000c0000000d0000000e0000000f0000000g0000000h0000000
+ 0000c0000000d0000000e0000000f0000000g0000000h0000000
  000000d0000000e0000000f0000000g0000000h0000000
  ────────────────────────────────────────────────────────────────
  a0b0c0d0b0c0d0e0c0d0e0f0d0e0f0g0e0f0g0h0f0g0h000g0h00000h0000000
& 1010101000000000000000000000000010101010000000000000000000000000
  ────────────────────────────────────────────────────────────────
  a0b0c0d0000000000000000000000000e0f0g0h0000000000000000000000000

这里可以看到输出组件。您可以更改编译器，看看它在各种架构上是如何工作的

在Bit Twiddling Hacks页面上也有另一种方法

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

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

相关:如何对像素数据进行位条带化？

如您所见，如果没有位存款指令的可用性，在操作方面将非常复杂。如果您执行非像这样的位条带化，那么最好使用 SIMD 并行执行