How can I shuffle bits efficiently?

Question

I need to shuffle a 16 bit unsigned integer in a way that the even indexes land in the lower byte, and the odd indexes land in the upper byte.

input:
fedcba98 76543210 (contiguously numbered)

output:
fdb97531 eca86420 (even and odd separated)

My code looks like this at the moment:

typedef unsigned short u16;

u16 segregate(u16 x)
{
    u16 g = (x & 0x0001);
    u16 h = (x & 0x0004) >> 1;
    u16 i = (x & 0x0010) >> 2;
    u16 j = (x & 0x0040) >> 3;
    u16 k = (x & 0x0100) >> 4;
    u16 l = (x & 0x0400) >> 5;
    u16 m = (x & 0x1000) >> 6;
    u16 n = (x & 0x4000) >> 7;

    u16 o = (x & 0x0002) << 7;
    u16 p = (x & 0x0008) << 6;
    u16 q = (x & 0x0020) << 5;
    u16 r = (x & 0x0080) << 4;
    u16 s = (x & 0x0200) << 3;
    u16 t = (x & 0x0800) << 2;
    u16 u = (x & 0x2000) << 1;
    u16 v = (x & 0x8000);

    return g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v;
}

I wonder if there is a more elegant solution than simply extracting and shifting each individual bit?

Answer 1

You could use a 256-byte table for each byte of your 16-bit number, crafted so that your even/odd condition is satisfied.

Ah yes, lookup tables to the rescue :) You can even do it with a single table and one extra shift:

u16 every_other[256] = {
0x00, 0x01, 0x00, 0x01, 0x02, 0x03, 0x02, 0x03, 
0x00, 0x01, 0x00, 0x01, 0x02, 0x03, 0x02, 0x03, 
0x04, 0x05, 0x04, 0x05, 0x06, 0x07, 0x06, 0x07, 
0x04, 0x05, 0x04, 0x05, 0x06, 0x07, 0x06, 0x07, 
0x00, 0x01, 0x00, 0x01, 0x02, 0x03, 0x02, 0x03, 
0x00, 0x01, 0x00, 0x01, 0x02, 0x03, 0x02, 0x03, 
0x04, 0x05, 0x04, 0x05, 0x06, 0x07, 0x06, 0x07, 
0x04, 0x05, 0x04, 0x05, 0x06, 0x07, 0x06, 0x07, 
0x08, 0x09, 0x08, 0x09, 0x0a, 0x0b, 0x0a, 0x0b, 
0x08, 0x09, 0x08, 0x09, 0x0a, 0x0b, 0x0a, 0x0b, 
0x0c, 0x0d, 0x0c, 0x0d, 0x0e, 0x0f, 0x0e, 0x0f, 
0x0c, 0x0d, 0x0c, 0x0d, 0x0e, 0x0f, 0x0e, 0x0f, 
0x08, 0x09, 0x08, 0x09, 0x0a, 0x0b, 0x0a, 0x0b, 
0x08, 0x09, 0x08, 0x09, 0x0a, 0x0b, 0x0a, 0x0b, 
0x0c, 0x0d, 0x0c, 0x0d, 0x0e, 0x0f, 0x0e, 0x0f, 
0x0c, 0x0d, 0x0c, 0x0d, 0x0e, 0x0f, 0x0e, 0x0f, 
0x00, 0x01, 0x00, 0x01, 0x02, 0x03, 0x02, 0x03, 
0x00, 0x01, 0x00, 0x01, 0x02, 0x03, 0x02, 0x03, 
0x04, 0x05, 0x04, 0x05, 0x06, 0x07, 0x06, 0x07, 
0x04, 0x05, 0x04, 0x05, 0x06, 0x07, 0x06, 0x07, 
0x00, 0x01, 0x00, 0x01, 0x02, 0x03, 0x02, 0x03, 
0x00, 0x01, 0x00, 0x01, 0x02, 0x03, 0x02, 0x03, 
0x04, 0x05, 0x04, 0x05, 0x06, 0x07, 0x06, 0x07, 
0x04, 0x05, 0x04, 0x05, 0x06, 0x07, 0x06, 0x07, 
0x08, 0x09, 0x08, 0x09, 0x0a, 0x0b, 0x0a, 0x0b, 
0x08, 0x09, 0x08, 0x09, 0x0a, 0x0b, 0x0a, 0x0b, 
0x0c, 0x0d, 0x0c, 0x0d, 0x0e, 0x0f, 0x0e, 0x0f, 
0x0c, 0x0d, 0x0c, 0x0d, 0x0e, 0x0f, 0x0e, 0x0f, 
0x08, 0x09, 0x08, 0x09, 0x0a, 0x0b, 0x0a, 0x0b, 
0x08, 0x09, 0x08, 0x09, 0x0a, 0x0b, 0x0a, 0x0b, 
0x0c, 0x0d, 0x0c, 0x0d, 0x0e, 0x0f, 0x0e, 0x0f, 
0x0c, 0x0d, 0x0c, 0x0d, 0x0e, 0x0f, 0x0e, 0x0f};

u16 segregate(u16 x)
{
    return every_other[x & 0xff]
         | every_other[(x >> 8)] << 4
         | every_other[(x >> 1) & 0xff] << 8
         | every_other[(x >> 9)] << 12;
}

Answer 2

The table approach shown by others is the most portable version and is probably quite fast.

If you want to take advantage of special instruction sets there are some other options as well. For Intel Haswell and later for example the following approach can be used (requires the BMI2 instruction set extension):

unsigned segregate_bmi (unsigned arg)
{
  unsigned oddBits  = _pext_u32(arg,0x5555);
  unsigned evenBits = _pext_u32(arg,0xaaaa);
  return (oddBits | (evenBits << 8));
}

Answer 3

your answer to the even and odd bits shuffle for 64 bits is not accurate. To extend the 16 bit solution to 64 bit solution, we need not only to extend the masks, but also cover the swapping interval from 1 all the way to 16:

x = bit_permute_step(x, 0x2222222222222222, 1);
x = bit_permute_step(x, 0x0c0c0c0c0c0c0c0c, 2);
x = bit_permute_step(x, 0x00f000f000f000f0, 4);
**x = bit_permute_step(x, 0x0000ff000000ff00, 8);
x = bit_permute_step(x, 0x00000000ffff0000, 16);**

Answer 4

Tables. But generate them at compile time!

namespace details {
  constexpr uint8_t bit( unsigned byte, unsigned n ) {
    return (byte>>n)&1;
  }
  constexpr uint8_t even_bits(uint8_t byte) {
    return bit(byte, 0) | (bit(byte, 2)<<1) | (bit(byte, 4)<<2) | (bit(byte, 6)<<3);
  }
  constexpr uint8_t odd_bits(uint8_t byte) {
    return even_bits(byte/2);
  }
  template<unsigned...>struct indexes{using type=indexes;};
  template<unsigned Max,unsigned...Is>struct make_indexes:make_indexes<Max-1,Max-1,Is...>{};
  template<unsigned...Is>struct make_indexes<0,Is...>:indexes<Is...>{};
  template<unsigned Max>using make_indexes_t=typename make_indexes<Max>::type;

  template<unsigned...Is>
  constexpr std::array< uint8_t, 256 > even_bit_table( indexes<Is...> ) {
    return { even_bits(Is)... };
  }
  template<unsigned...Is>
  constexpr std::array< uint8_t, 256 > odd_bit_table( indexes<Is...> ) {
    return { odd_bits(Is)... };
  }
  constexpr std::array< uint8_t, 256 > even_bit_table() {
    return even_bit_table( make_indexes_t<256>{} );
  }
  constexpr std::array< uint8_t, 256 > odd_bit_table() {
    return odd_bit_table( make_indexes_t<256>{} );
  }

  static constexpr auto etable = even_bit_table();
  static constexpr auto otable = odd_bit_table();
}

uint8_t constexpr even_bits( uint16_t in ) {
  return details::etable[(uint8_t)in] | ((details::etable[(uint8_t)(in>>8)])<<4);
}
uint8_t constexpr odd_bits( uint16_t in ) {
  return details::otable[(uint8_t)in] | ((details::otable[(uint8_t)(in>>8)])<<4);
}

live example

Answer 5

In favour of being short:

unsigned short segregate(unsigned short x)
{
    x = (x & 0x9999) | (x >> 1 & 0x2222) | (x << 1 & 0x4444);
    x = (x & 0xC3C3) | (x >> 2 & 0x0C0C) | (x << 2 & 0x3030);
    x = (x & 0xF00F) | (x >> 4 & 0x00F0) | (x << 4 & 0x0F00);
    return x;
}

Answer 6

You could use a 256-byte table for each byte of your 16-bit number, crafted so that your even/odd condition is satisfied. Hand-code the table entries (or use the algorithm you already have) to create the tables, and then the shuffling will be done at compile time. That would essentially be a translation table concept.