如何解交织比特(UnMortonizing？)

Question

从32位int解交织比特的最有效方法是什么？对于这种特殊情况,我只关注奇数位,尽管我确信将两个集合的任何解决方案概括为简单.

例如,我想转换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

然后第二步一次使用两位,依此类推.