How to de-interleave bits (UnMortonizing?)

Question

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?

Answer 1

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.

Answer 2

In terms of speed, a lookup table 16 bits wide with 2^32 entries will be hard to beat! But if you don't have that much memory to spare, four lookups in a 256-entry table, plus a few shifts and ANDs to stitch them together, might be a better choice. Or perhaps the sweet spot is somewhere in between...it depends on the resources you have available, and how the cost of initializing the lookup table will be amortized over the number of lookups you need to perform.