How to disintegrate bits (UnMortonizing?)

Question

What is the most efficient way to deinterlace bits from a 32 bit int? In this particular case, I only care about the odd bits, although I'm sure it's easy to generalize any solution to both sets.

For example, I want to convert 0b01000101 to 0b1011 . What is the fastest way?

EDIT:

In this application, I can guarantee that even bits are all zeros. Can I use this 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 is as follows:

  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, etc.

Answer 2

In terms of speed, a 16-bit wide lookup table with 2 ^ 32 inputs will be hard to beat! But if you don't have much memory, four searches in a table with 256 inputs, plus a few offsets and AND to stitch them together, might be the best choice. Or maybe the sweet spot is somewhere in the middle ... it depends on your resources and how the cost of initializing the lookup table will be amortized by the number of queries that need to be completed.

Answer 3

I'm not sure how fast it would be, but you could do something like

 int a = 0b01000101; int b = 0; int i = 0; while (a > 0) { b |= (a & 1) << i; a >>= 2; } 

To get all the odd bits out of a and put them on b.