代码之家 › 专栏 › 技术社区 › AShelly

如何取消位的交织(取消交织?)

z-order-curve bit-manipulation

22

AShelly · 技术社区 · 15 年前

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

例如,我想转换 0b01000101 进入之内 0b1011

编辑:

3 回复 | 直到 7 年前

1

34

Matthew Slattery 15 年前

假设您知道应用程序中的每一位都是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

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

2

1

Jim Lewis 15 年前

就速度而言,一个16位宽、有2^32个条目的查找表将很难被打败! 如何将初始化查找表的成本分摊到需要执行的查找数上。

3

0

Mike Cooper 15 年前

快的

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

它会把a的所有奇数都取出来,放到b上。