位摆弄黑客：以明显的方式交错位

发布于 2024-09-09 00:16:51 字数 667 浏览 3 评论 0原文

我对这个问题感兴趣

以明显的方式交错位

（来自 http://graphics.stanford.edu/~seander/bithacks.html< /a>)

无符号短x； // 交错 x 和 y 的位，以便所有的
无符号短 y； // x 的位位于偶数位置，y 位于奇数位置；
无符号整数 z = 0； // z 获取生成的莫顿数。

for (int i = 0; i < sizeof(x) * CHAR_BIT; i++) // 展开以获得更快的速度...
{
  z |= (x & 1U << i) <<我| (y&1U＜＜i)＜＜ (i+1)；
}

有人可以通过示例向我解释这是如何工作的吗？

例如，如果我们有 x = 100101 和 y = 010101，结果会是什么？

原文

i am interested on this problem

Interleave bits the obvious way

(from 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);
}

can someone explain to me how this works with an example?

for example if we have x = 100101 and y = 010101, what will be result?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

江南烟雨〆相思醉 2024-09-16 00:16:51

位交织本质上采用两个 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 中的位进入偶数索引 (0, 2, 4...)奇数索引 (1, 3, 5...)。也就是说，位交织不是可交换操作； interleave(x, y) 通常不等于 interleave(y, x)。

您还可以将位交织操作推广到不仅仅涉及 2 个数字。

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

另请参阅

Wikipedia/Z-order（曲线）
- 又名莫顿秩序/莫顿代码

“显而易见”的算法

该算法本质上会遍历输入数字的每一位，通过按位与检查它是 1 还是 0，然后将两者组合起来位与按位或，并通过适当的移位将它们连接在一起。

要了解这些位是如何重新排列的，只需看一个简单的 4 位示例即可。这里xi表示x的第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"

另请参阅

维基百科/按位运算

Bit interleaving essentially takes two n bit input numbers and produces one 2n bit output number that alternately takes bits from the two input numbers. That is, bits from one number goes into the odd indices, and bits from the other goes into the even indices.

So for your specific example:

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

interleaved = 011000110011

Here we use the convention that bits from x goes into the even indices (0, 2, 4...) and bits from y goes into the odd indices (1, 3, 5...). That is, bit interleaving is not a commutative operation; interleave(x, y) is generally not equal to interleave(y, x).

You can also generalize the bit interleaving operation to involve more than just 2 numbers.

Bit-interleaved numbers exhibit structural properties that can be taken advantage of in many important spatial algorithms/data structures.

"Obvious" algorithm

The algorithm essentially goes through every bits of the input numbers, checking if it's 1 or 0 with bitwise-and, combining the two bits with bitwise-or, and concatenating them together with proper shifts.

To understand how the bits are rearranged, just work on a simple 4-bit example. Here xi denotes the i-th (0-based) bit of 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]

Once you convinced yourself that the mapping pattern is correct, implementing it is simply a matter of understanding how bitwise operations are performed.

Here's the algorithm rewritten in Java for clarity (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"