Bit Twiddling Hacks: interleave bits the obvious way

Question

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?

Answer 1

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

Answer 2

"Interleaving" means that you combine the two numbers by alternating bits from each source. It's easier to see with the following example

x = 0000
y = 1111

result = 01010101

Interleaving the two values you've given gives the following result:

x = 100101 
y = 010101

result = 100100110011