c - Bit Twiddling Hacks:交织比特的明显方法

我对这个问题感兴趣
交错位
（来自http://graphics.stanford.edu/~seander/bithacks.html）

unsigned short x;   // Interleave bits of x and y, so that all of the
unsigned short y;   // bits of x are in the even positions and y in the odd;
unsigned int z = 0; // z gets the resulting Morton Number.

for (int i = 0; i < sizeof(x) * CHAR_BIT; i++) // unroll for more speed...
{
  z |= (x & 1U << i) << i | (y & 1U << i) << (i + 1);
}

有人能给我举个例子解释一下这是怎么回事吗？
例如，如果我们有x = 100101和y = 010101，结果会是什么？

最佳答案

位交织实质上取两个n位输入数并产生一个2n位输出数，该位输出数交替取两个输入数中的位。也就是说，一个数的位进入奇数索引，另一个数的位进入偶数索引。
所以对于你的具体例子：

x = 100101  =  1 0 0 1 0 1
y = 010101  = 0 1 0 1 0 1

interleaved = 011000110011

这里我们使用的约定是，x的位进入偶数索引（0，2，4…），而y的位进入奇数索引（1，3，5…）。也就是说，比特交织不是commutative操作；interleave(x, y)通常不等于interleave(y, x)。
您还可以将位交织操作概括为包含两个以上的数字。
位交织数具有许多重要的空间算法/数据结构可以利用的结构特性。
另见
Wikipedia/Z-order (curve)
又名莫顿订单/莫顿代码
相关问题
How to compute a 3D Morton number (interleave the bits of 3 ints)
How to de-interleave bits (UnMortonizing?)
“明显”算法
该算法基本上遍历输入数字的每一位，用逐位和检查它是1还是0，用逐位或组合这两个位，并用适当的移位将它们连接起来。
要了解这些位是如何重新排列的，只需处理一个简单的4位示例。这里xi表示i的第x-位（0位）。

x =    x3    x2    x1    x0
y = y3    y2    y1    y0
                                         Mapping:
z = y3 x3 y2 x2 y1 x1 y0 x0                 x[i] --> z[i+i]
    z7 z6 z5 z4 z3 z2 z1 z0                 y[i] --> y[i+i+1]

一旦您确信映射模式是正确的，那么实现它只是理解如何执行按位操作的问题。
下面是为清晰起见用Java重写的算法（see also on ideone.com）：

    int x = Integer.parseInt("100101", 2);
    int y = Integer.parseInt("010101", 2);
    int z = 0;

    for (int i = 0; i < Integer.SIZE; i++) {
       int x_masked_i = (x & (1 << i));
       int y_masked_i = (y & (1 << i));

       z |= (x_masked_i << i);
       z |= (y_masked_i << (i + 1));
    }
    System.out.println(Integer.toBinaryString(z));
    // prints "11000110011"

另见
Wikipedia/Bitwise operations

关于c - Bit Twiddling Hacks:交织比特的明显方法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/3203764/