bit-manipulation - 如何解交织位(取消Mortonizing？)

从32位整数解交织位的最有效方法是什么？对于这种特殊情况，我只关心奇数位，尽管我敢肯定，将所有解决方案归纳到这两个集合很简单。

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

编辑:

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

最佳答案

假设您知道应用程序中的其他所有位均为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

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