位操作黑客：交错位的明显途径 [英] Bit Twiddling Hacks: interleave bits the obvious way

问题描述

我有兴趣在这个问题上

  

交错位明显的方式

  
  

（从<一个href=\"http://graphics.stanford.edu/~seander/bithacks.html\">http://graphics.stanford.edu/~seander/bithacks.html)

 无符号短X; x和y的//交错位，使得所有的
无符号短ÿ; // x的位在奇数偶数位置和y;
unsigned int类型Z = 0; //ž得到结果莫顿数。的for（int i = 0; I＆LT;的sizeof（X）* CHAR_BIT;我++）//展开更多的速度...  - 
{
  ž| =（X安培; 1U＆LT;＆LT; I）LT;＆LT;我| （Y＆安培; 1U＆LT;＆LT; I）LT;＆LT;第（i + 1）;
}
 

有人可以给我解释一下这是如何工作用一个例子？

例如，如果我们有 X = 100101 和 Y = 010101 ，究竟会导致？

解决方案

比特交织基本上需要两个 N 位输入数字，生成一个 2N < /交替取位时，从两个输入编号code>位输出数量。即，位从一个号码进入奇数索引，并从其他位进入偶数索引

因此​​，对于你具体的例子：

  X = 100101 = 1 0 0 1 0 1
Y = 010101 = 0 1 0 1 0 1交错= 011000110011
 

下面我们使用从位X 进入偶数索引（0，2，4 ...）和位时，从 y中的约定进入奇数索引（1，3，5 ...）。即，比特交织不是​​可交换操作; 交错（X，Y）一般不等于交错（Y，X）。

您也可以概括比特交织操作不仅仅是2号的更多参与。

比特交织的数字表现，可以在许多重要的空间算法/数据结构被利用的结构性能。

另请参见

• 维基百科/ Z轴顺序（曲线）
  
  
  
  • 又名莫顿订单/莫顿code
  
  

相关问题

• How计算一个3D莫顿号（交错的3个整数位）


• 如何去交织位（UnMortonizing？）

---

显而易见的算法

该算法基本上是经过输入数字的每一个位，检查是否是1或0按位和中，两位与按位或组合，以及适当的变化一起串联它们。

要了解位是如何重新排列，只是一个简单的4位例子工作。在这里，喜表示 我 -th（从0开始）位x 。

  X = X3 X2 X1 X0
Y = Y3 Y2 Y1 Y0
                                         制图：
Z = Y3 X3 Y2 X2 Y1 X1 Y0 X0 X [I]  - ＆GT; Z [我+ I]
    Z7 Z6 Z5 Z4 Z3 Z2 Z1 Z0值Y [i]  - ＆GT;值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＆LT; Integer.SIZE;我++）{
       INT x_masked_i =（X及（1下;＆下;ⅰ））;
       INT y_masked_i =（Y及（1下;＆下;ⅰ））;       ž| =（x_masked_i＆LT;＆LT;我）;
       ž| =（y_masked_i＆所述;＆下;第（i + 1））;
    }
    的System.out.println（Integer.toBinaryString（Z））;
    //输出11000110011
 

另请参见

• 维基/位运算

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?

解决方案

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.

See also

• Wikipedia/Z-order (curve)
  • aka Morton-Order/Morton code

Related questions

• How to compute a 3D Morton number (interleave the bits of 3 ints)
• How to de-interleave bits (UnMortonizing?)

---

"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"

See also

• Wikipedia/Bitwise operations

这篇关于位操作黑客：交错位的明显途径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！