bit-manipulation - 如何去交错位（UnMortonizing？）

Question

从 32 位整数中解交织位的最有效方法是什么？对于这种特殊情况，我只关心奇数位，尽管我确信将任何解决方案推广到两组都很简单。

例如，我想转换0b01000101为0b1011. 最快的方法是什么？

编辑：

在这个应用程序中，我可以保证偶数位全为零。我可以利用这一事实来提高速度或减少空间吗？

Answer 1

假设您知道应用程序中的所有其他位都是 0，您可以这样做：

x = (x | (x >> 1)) & 0x33333333;
x = (x | (x >> 2)) & 0x0f0f0f0f;
x = (x | (x >> 4)) & 0x00ff00ff;
x = (x | (x >> 8)) & 0x0000ffff;

第一步如下所示：

  0a0b0c0d0e0f0g0h0i0j0k0l0m0n0o0p   x
| 00a0b0c0d0e0f0g0h0i0j0k0l0m0n0o0   x >> 1
  --------------------------------
= 0aabbccddeeffgghhiijjkkllmmnnoop   x | (x >> 1)
& 00110011001100110011001100110011   0x33333333
  --------------------------------
= 00ab00cd00ef00gh00ij00kl00mn00op   (x | (x >> 1)) & 0x33333333

然后第二步一次使用两个位，依此类推。

Answer 2

在速度方面，一个 16 位宽的 2^32 个条目的查找表将很难被击败！但是，如果您没有那么多可用内存，那么在一个 256 条目的表中进行四次查找，再加上一些移位和 AND 将它们拼接在一起，可能是一个更好的选择。或者，最佳点可能介于两者之间……这取决于您可用的资源，以及如何将初始化查找表的成本摊销到您需要执行的查找次数上。

Answer 3

我不确定它会有多快，但你可以做类似的事情

int a = 0b01000101;
int b = 0;
int i = 0;
while (a > 0) {
    b |= (a & 1) << i;
    a >>= 2;
}

这会将所有奇数位从 a 中拉出并放在 b 上。