有效地交织位 [英] Interleave bits efficiently

问题描述

我需要让 uint64_t 输出2 uint32_t 交错位：if A = a0a1a2 ... a31 和 B = b0b1 ... b31 ，我需要C = a0b0a1b1 ... a31b31 有办法有效地做到这一点吗？到目前为止，我只有一个用于32次迭代的循环的朴素方法，其中每次迭代 C | =（（A& ;< i））<< i）|（（B&（1< i））<（i + 1））。 b

我想应该有一些数学诡计，例如将A和B乘以一个特殊的数字，结果是它们的位在所得到的64位数字中与零交织，所以只剩下的是或这些产品。但是我找不到这样的乘法器。

另一个潜在的方法是编译器内在或汇编指令，但我不知道。

解决方案

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

  static const unsigned int B [] = {0x55555555，0x33333333，0x0F0F0F0F，0x00FF00FF}; 
 static const unsigned int S [] = {1,2,4，8}; 
 
 unsigned int x; //交织x和y的低16位，所以x 
的位无符号整数; //在偶数位置，位从奇数中的y; 
 unsigned int z; // z得到的32位Morton数。 
 // x和y必须初始地小于65536. 
 
 x =（x |（x  x =（x |（x << S [2]））& B [2]; 
 x =（x |（x << S [1]））& B [1]; 
 x =（x |（x << S [0]））& B [0]; 
 
 y = [y上的同一件事] 
 
 z = x | （y <1）; 
  

适用于：

1. 保留x的低8位。将高8位向上移动8;


2. 分割一半并执行相同的操作，此时保留4位的低对，并将其他位移4; / li>
   
3. 又一次。

它继续如下：

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

然后将两个输入合并。

$ b b

根据我之前的注释，要将其扩展为64位，只需要将初始位移增加16，然后屏蔽 0x0000ffff0000ffff ，因为您可以直观地遵循模式或作为一个分而治之的步骤，将32位问题转换成两个非重叠的16位问题，然后使用16位解决方案。

I need to make uint64_t out of 2 uint32_t interleaving the bits: if A=a0a1a2...a31 and B=b0b1...b31, I need C=a0b0a1b1...a31b31. Is there a way to do this efficiently? So far I've got only the naive approach with a for loop of 32 iterations, where each iteration does C|=((A&(1<<i))<<i)|((B&(1<<i))<<(i+1)).

I guess there should be some mathematical trick like multiplying A and B by some special number which results in interleaving their bits with zeros in the resulting 64-bit number, so that what only remains is to or these products. But I can't find such multiplier.

Another potential way to go is a compiler intrinsic or assembly instruction, but I don't know of such.

解决方案

NathanOliver's link offers the 16-bit -> 32-bit implementation:

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);

Which works by:

1. leave the low 8 bits of x where they are. Move the high 8 bits up by 8;
2. divide in half and do the same thing, this time leaving the low pairs of 4 bits where they are and moving the others up by 4;
3. and again, and again.

I.e. it proceeds as:

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

And then combines the two inputs together.

As per my earlier comment, to extend that to 64 bits, just add an initial shift by 16 and mask by 0x0000ffff0000ffff, either because you can intuitively follow the pattern or as a divide-and-conquer step, turning the 32-bit problem into two non-overlapping 16-bit problems and then using the 16-bit solution.

这篇关于有效地交织位的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！