Bit Twiddling Hacks: interleave bits the obvious way [closed]_问答_开发者

Bit Twiddling Hacks: interleave bits the obvious way [closed]

开发者 https://www.devze.com 2023-01-06 15:42 出处：网络

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical andcannot be reasonably answered in its current form. For help clari

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center. 开发者_开发知识库 Closed 12 years ago.

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.

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