bit-manipulationz-order-curve

How to de-interleave bits (UnMortonizing?)

What is the most efficient way to de-interleave bits from a 32 bit int? For this particular case, I'm only concerned about the odd bits, although I'm sure it's simple to generalize any solution to both sets.

For example, I want to convert 0b01000101 into 0b1011. What's the quickest way?

EDIT:

In this application, I can guarantee that the even bits are all zeros. Can I take advantage of that fact to improve speed or reduce space?

Solution

  • Given that you know that every other bit is 0 in your application, you can do it like this:

    x = (x | (x >> 1)) & 0x33333333;
x = (x | (x >> 2)) & 0x0f0f0f0f;
x = (x | (x >> 4)) & 0x00ff00ff;
x = (x | (x >> 8)) & 0x0000ffff;

    The first step looks like this:

      0a0b0c0d0e0f0g0h0i0j0k0l0m0n0o0p   x
| 00a0b0c0d0e0f0g0h0i0j0k0l0m0n0o0   x >> 1
  --------------------------------
= 0aabbccddeeffgghhiijjkkllmmnnoop   x | (x >> 1)
& 00110011001100110011001100110011   0x33333333
  --------------------------------
= 00ab00cd00ef00gh00ij00kl00mn00op   (x | (x >> 1)) & 0x33333333

    Then the second step works with two bits at a time, and so on.