有效地交织比特

Question

我需要做出uint64_t2个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. 又一次又一次.

即它继续如下:

abcdefghijklmnop
-> 00000000abcdefgh 00000000ijklmnop
-> 0000abcd0000efgh 0000ijkl0000mnop
-> 00ab00cd00ef00gh 00ij00kl00mn00op
-> 0a0b0c0d0e0f0g0h 0i0j0k0l0m0n0o0p

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

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

Answer 2

对于较大的整数，值得一提的是有限域乘法（无进位乘法）的 clmul x86 扩展。将整数与零交织相当于整数与自身的无进位乘法，这是一条 ALU 指令。