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 = 100101、y = 010101結果はどうなるでしょうか。

4

2 に答える 2

18

ビット インターリーブは、基本的に 2 つのnビット入力数を取り、2 つの入力数から交互にビットを取得する 1 つの2nビット出力数を生成します。つまり、1 つの数値からのビットは奇数インデックスに入り、別の数値からのビットは偶数インデックスに入ります。

したがって、特定の例については：

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

interleaved = 011000110011

ここでは、 からのビットが偶数インデックス ( x0、2、4...) に入り、 からのビットyが奇数インデックス (1、3、5...) に入るという規則を使用します。つまり、ビット インターリーブは可換演算ではありません。interleave(x, y)は一般に と等しくありませんinterleave(y, x)。

ビット インターリーブ操作を一般化して、2 つ以上の数値を含めることもできます。

ビット インターリーブ数は、多くの重要な空間アルゴリズム/データ構造で利用できる構造特性を示します。

こちらもご覧ください

関連する質問

「明白な」アルゴリズム

アルゴリズムは基本的に、入力数値のすべてのビットを調べて、それが 1 か 0 かをビットごとの AND でチェックし、2 つのビットをビットごとの OR で結合し、適切なシフトでそれらを連結します。

ビットがどのように再配置されるかを理解するには、単純な 4 ビットの例に取り組んでください。ここでxiは、 のi- 番目 (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

「インターリーブ」とは、各ソースからのビットを交互に並べて 2 つの数値を結合することを意味します。次の例を見るとわかりやすい

x = 0000
y = 1111

result = 01010101

指定した 2 つの値をインターリーブすると、次の結果が得られます。

x = 100101 
y = 010101

result = 100100110011
于 2010-07-08T13:02:41.940 に答える