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 …）。 也就是说，比特交织不是可交换操作; interleave(x, y)通常不等于interleave(y, x) 。
您还可以将比特交错操作概括为不仅仅涉及2个数字。
比特交织数表现出可以在许多重要的空间算法/数据结构中利用的结构特性。
也可以看看
- 维基百科/ Z顺序（曲线）
- 又名Morton-Order / Morton代码
相关问题
- 如何计算3D Morton数（交错3个整数的位）
- 如何解交织比特（UnMortonizing？）
“明显”的算法
该算法基本上遍历输入数字的每个位，用位按顺序检查它是1还是0，并将这两位用位按位组合，或者用适当的移位将它们连接在一起。
要了解这些位是如何重新排列的，只需要处理一个简单的4位示例。 这里xi表示xi第i （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重写的算法（ 另见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"
也可以看看
- 维基百科/按位运算
“交错”意味着您通过交替来自每个源的位来组合这两个数字。 通过以下示例更容易看到
x = 0000 y = 1111 result = 01010101
交错您给出的两个值会得到以下结果：
x = 100101 y = 010101 result = 100100110011