17

我对这个问题很感兴趣

交错位是显而易见的方式

（来自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 = 100101and y = 010101，结果会是什么？

4

2 回答 2

18

位交错本质上采用两位n输入数并产生一位2n输出数，该输出数交替地从两个输入数中取出位。也就是说，来自一个数字的位进入奇数索引，而来自另一个数字的位进入偶数索引。

因此，对于您的具体示例：

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

interleaved = 011000110011

在这里，我们使用的约定是，位 fromx进入偶数索引 (0, 2, 4...)，位 fromy进入奇数索引 (1, 3, 5...)。也就是说，比特交织不是​​交换操作；interleave(x, y)一般不等于interleave(y, x)。

您还可以将位交错操作概括为不仅仅涉及 2 个数字。

比特交错数字表现出可以在许多重要的空间算法/数据结构中利用的结构特性。

也可以看看

相关问题

“显而易见”的算法

该算法基本上遍历输入数字的每一位，用按位与检查它是 1 还是 0，用按位或组合这两个位，并用适当的移位将它们连接在一起。

要了解这些位是如何重新排列的，只需处理一个简单的 4 位示例。这里xi表示 的i第 -th（从 0 开始）位x。

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"

也可以看看

于 2010-07-08T12:59:27.023 回答
3

“交错”意味着您通过交替来自每个源的位来组合这两个数字。使用以下示例更容易看到

x = 0000
y = 1111

result = 01010101

交错您给出的两个值会得到以下结果：

x = 100101 
y = 010101

result = 100100110011
于 2010-07-08T13:02:41.940 回答