Bitwise extension in C ++

Question

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

short a; short b; 

Their bit representation can be placed as

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

Where a0, b0, a1, b1, etc. represent separate bits for two short ints. Now I would like to know if there is an efficient way to create an int in the form:

 a0 b0 a1 b1 a2 b2 ... a15 b15 

I know that I could pedantically use a loop and manually bitmask each bit, but I wanted to know if there is a more efficient way to do this.

Many thanks

Answer 1

Here is one way using the 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 generalized to wider inputs.

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

For the background, this alternation of bits is called the Morton code and is a way of combining several dimensions into one, preserving the terrain of the points.

Answer 2

I would go with a for loop and run an algorithm.

 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 is working correctly, enable the optimization level. The compiler can perform some amazing optimizations, such as looping around.

You can also search the Internet for “bit twiddling” and see if any of these cases are similar.

Answer 3

Here is 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; } 

Conclusion:

 a: 1010101111001101 b: 0001001000110100 merged: 10001001100011101010010110110010