c++ - 有效地交织位

Question

我需要制作 uint64_t满分 2 uint32_t交错位:如果 A=a0a1a2...a31和 B=b0b1...b31 , 我需要 C= a0b0a1b1...a31b31 .有没有办法有效地做到这一点？到目前为止，我只有使用 for 的天真方法。 32 次迭代的循环，其中每次迭代执行 C|=((A&(1<<i))<<i)|((B&(1<<i))<<(i+1)) .

我想应该有一些数学技巧，比如将 A 和 B 乘以某个特殊数字，这会导致在结果 64 位数字中将它们的位与零交织，所以剩下的就是 or这些产品。但是我找不到这样的乘数。

另一种可能的方法是编译器内部或汇编指令，但我不知道这样的。

Answer 1

NathanOliver 的链接提供了 16 位 -> 32 位实现:

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 = [the same thing on y]

z = x | (y << 1);

它的工作原理是:

1. 将 x 的低 8 位保留在原处。将高 8 位向上移动 8；
2. 分成两半并做同样的事情，这次将低 4 位对留在原处，并将其他 4 位向上移动；
3. 一次又一次。

即它是这样进行的:

   0000 0000 0000 0000  abcd efgh ijkl mnop
-> 0000 0000 abcd efgh  0000 0000 ijkl mnop
-> 0000 abcd 0000 efgh  0000 ijkl 0000 mnop
-> 00ab 00cd 00ef 00gh  00ij 00kl 00mn 00op
-> 0a0b 0c0d 0e0f 0g0h  0i0j 0k0l 0m0n 0o0p

然后将两个输入组合在一起。

根据我之前的评论，要将其扩展到 64 位，只需将初始移位添加 16 位并添加 0x0000ffff0000ffff 掩码，因为您可以直观地遵循该模式或作为分而治之征服步骤，将32位问题转化为两个不重叠的16位问题，然后使用16位解决方案。