Bitwise expansion in C++

Question

here is my problem. I have two short ints in C++:

short a;
short b;

Their bit representation can be put in the form

a = a0 a1 a2 a3 a4 ... a15
b = b0 b1 b2 b3 b4 ... b15

Where a0, b0, a1, b1 and so on represent the single bits for the two short ints. Now, I would like to know if there is an efficient way to produce an int in the form:

a0 b0 a1 b1 a2 b2 ... a15 b15

I know I could pedantically use a loop and manually bitmasking every single bit, but I wanted to know if there is a more efficient way to do it.

Thank you very much

Answer 1

Here is one way, with a lookup table:

static const unsigned short MortonTable256[256] = 
{
  0x0000, 0x0001, 0x0004, 0x0005, 0x0010, 0x0011, 0x0014, 0x0015, 
  0x0040, 0x0041, 0x0044, 0x0045, 0x0050, 0x0051, 0x0054, 0x0055, 
  0x0100, 0x0101, 0x0104, 0x0105, 0x0110, 0x0111, 0x0114, 0x0115, 
  0x0140, 0x0141, 0x0144, 0x0145, 0x0150, 0x0151, 0x0154, 0x0155, 
  0x0400, 0x0401, 0x0404, 0x0405, 0x0410, 0x0411, 0x0414, 0x0415, 
  0x0440, 0x0441, 0x0444, 0x0445, 0x0450, 0x0451, 0x0454, 0x0455, 
  0x0500, 0x0501, 0x0504, 0x0505, 0x0510, 0x0511, 0x0514, 0x0515, 
  0x0540, 0x0541, 0x0544, 0x0545, 0x0550, 0x0551, 0x0554, 0x0555, 
  0x1000, 0x1001, 0x1004, 0x1005, 0x1010, 0x1011, 0x1014, 0x1015, 
  0x1040, 0x1041, 0x1044, 0x1045, 0x1050, 0x1051, 0x1054, 0x1055, 
  0x1100, 0x1101, 0x1104, 0x1105, 0x1110, 0x1111, 0x1114, 0x1115, 
  0x1140, 0x1141, 0x1144, 0x1145, 0x1150, 0x1151, 0x1154, 0x1155, 
  0x1400, 0x1401, 0x1404, 0x1405, 0x1410, 0x1411, 0x1414, 0x1415, 
  0x1440, 0x1441, 0x1444, 0x1445, 0x1450, 0x1451, 0x1454, 0x1455, 
  0x1500, 0x1501, 0x1504, 0x1505, 0x1510, 0x1511, 0x1514, 0x1515, 
  0x1540, 0x1541, 0x1544, 0x1545, 0x1550, 0x1551, 0x1554, 0x1555, 
  0x4000, 0x4001, 0x4004, 0x4005, 0x4010, 0x4011, 0x4014, 0x4015, 
  0x4040, 0x4041, 0x4044, 0x4045, 0x4050, 0x4051, 0x4054, 0x4055, 
  0x4100, 0x4101, 0x4104, 0x4105, 0x4110, 0x4111, 0x4114, 0x4115, 
  0x4140, 0x4141, 0x4144, 0x4145, 0x4150, 0x4151, 0x4154, 0x4155, 
  0x4400, 0x4401, 0x4404, 0x4405, 0x4410, 0x4411, 0x4414, 0x4415, 
  0x4440, 0x4441, 0x4444, 0x4445, 0x4450, 0x4451, 0x4454, 0x4455, 
  0x4500, 0x4501, 0x4504, 0x4505, 0x4510, 0x4511, 0x4514, 0x4515, 
  0x4540, 0x4541, 0x4544, 0x4545, 0x4550, 0x4551, 0x4554, 0x4555, 
  0x5000, 0x5001, 0x5004, 0x5005, 0x5010, 0x5011, 0x5014, 0x5015, 
  0x5040, 0x5041, 0x5044, 0x5045, 0x5050, 0x5051, 0x5054, 0x5055, 
  0x5100, 0x5101, 0x5104, 0x5105, 0x5110, 0x5111, 0x5114, 0x5115, 
  0x5140, 0x5141, 0x5144, 0x5145, 0x5150, 0x5151, 0x5154, 0x5155, 
  0x5400, 0x5401, 0x5404, 0x5405, 0x5410, 0x5411, 0x5414, 0x5415, 
  0x5440, 0x5441, 0x5444, 0x5445, 0x5450, 0x5451, 0x5454, 0x5455, 
  0x5500, 0x5501, 0x5504, 0x5505, 0x5510, 0x5511, 0x5514, 0x5515, 
  0x5540, 0x5541, 0x5544, 0x5545, 0x5550, 0x5551, 0x5554, 0x5555
};

unsigned short x; // Interleave bits of x and y, so that all of the
unsigned short y; // bits of x are in the even positions and y in the odd;
unsigned int z;   // z gets the resulting 32-bit Morton Number.

z = MortonTable256[y >> 8]   << 17 | 
    MortonTable256[x >> 8]   << 16 |
    MortonTable256[y & 0xFF] <<  1 | 
    MortonTable256[x & 0xFF];

The lookup table converts the 8-bit binary number abcdefgh to 0a0b0c0d0e0f0g0h. The code works for 16-bit inputs (and 32-bit output), but can be easily generalised for wider inputs.

The code is taken from Bit Twiddling Hacks. See the link for two other methods.

For background, this interleaving of bits is called the Morton code and is a way to combine multiple dimensions into one while preserving locality of points.

Answer 2

I would go with a for loop and get the algorithm working.

uint32_t result = 0;
uint16_t a;
uint16_t b;

const unsigned int bits_to_process = 16;

for (unsigned int i = 0; i < bits_to_process; ++i)
{
  result = a & 1;
  result << 1;
  result = b & 1;
  result << 1;
  a = a >> 1;
  b = b >> 1;
}

Once your code works correctly, turn up the optimization level. The compiler may perform some amazing optimizations, like loop unrolling.

You could also search the web for "bit twiddling" and see if any of those cases are like yours.

Answer 3

Here's how I would do it..

#include <iostream>
#include <bitset>

using namespace std;

inline unsigned int
move_bit(unsigned short x, int pos, int count)
{
    return (x & (1 << pos)) << count;
}

inline unsigned int
merge_bits(unsigned short a, unsigned short b)
{
    unsigned int res{};

    for(int i=0; i<16; i++)
        res |= (move_bit(a, i, i+1) | move_bit(b, i, i));

    return res;
}

int main()
{
    unsigned short a = 0xabcd;
    unsigned short b = 0x1234;
    unsigned int   c = merge_bits(a, b);

    cout << "a:      " << bitset<16>(a) << endl
         << "b:      " << bitset<16>(b) << endl
         << "merged: " << bitset<32>(c) << endl;
}

Output:

a:      1010101111001101
b:      0001001000110100
merged: 10001001100011101010010110110010