25

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?

Paul R
  • 208,748
  • 37
  • 389
  • 560
AShelly
  • 34,686
  • 15
  • 91
  • 152

3 Answers3

38

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.

Matthew Slattery
  • 45,290
  • 8
  • 103
  • 119
  • this tests faster than a 32 entry table on my PC. – AShelly Jul 16 '10 at 23:07
  • 5
    …and if you don't know that the odd bits are zero, do `x &= 0x55555555` in before – Bergi Jun 19 '15 at 05:43
  • Note: the supplied function counts the even bits that are set, whereas in the original question it was counting odd bits. You can count odd bits using this func by shifting right by 1 first. – jwd Feb 10 '21 at 01:31
1

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.

Jim Lewis
  • 43,505
  • 7
  • 82
  • 96
  • 1
    I definitely don't have that much memory to spare - I'm targeting an embedded platform. The 256 entry table might work. I'm still interested in an algorithmic method. – AShelly Jun 29 '10 at 22:47
  • @AShelly: a starting point would be to think about how many positions each potential one-bits would have to "move" (shift) into the new position. For example, bit 6 would be shifted right by 3 places, bit 4 by 2 places, bit 2 by 1 places, and bit 0 without shifting. Then, decompose those shift amounts into binary number. This works because shifting by, say, 3 places is the same as shifting by 2 and then again by 1. Use a bit mask to select the bits that needs to be shifted. This approach could be more costly than a small lookup table, though. – rwong Jul 05 '10 at 12:32
  • on embedded platform, try a 16-entry table and process 4-bits at a time. – rwong Jul 05 '10 at 12:34
0

I'm not sure how quick 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;
}

Which would pull all the odd bits off of a and put them on b.

Mike Cooper
  • 2,928
  • 2
  • 26
  • 29