Espansione bitwise in C++

Question

ecco il mio problema. Ho due interi brevi in ​​C++:

short a; 
short b; 

loro rappresentazione bit può essere messo nella forma

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

Dove a0, b0, a1, b1 e così via rappresentano singoli bit per i due brevi int. Ora, vorrei sapere se c'è un modo efficiente per produrre un int nella forma:

a0 b0 a1 b1 a2 b2 ... a15 b15 

So che potrei pedante utilizzare un ciclo e bitmasking manualmente ogni singolo bit, ma volevo sapere se c'è un modo più efficiente per farlo.

La ringrazio molto

Answer 1

Ecco un modo, con una tabella di ricerca:

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]; 

La tabella di ricerca converte la 8-bit numero binario abcdefgh-0a0b0c0d0e0f0g0h. Il codice funziona per ingressi a 16 bit (e uscita a 32 bit), ma può essere facilmente generalizzato per ingressi più ampi.

Il codice è preso da Bit Twiddling Hacks. Vedi il link per altri due metodi.

Per lo sfondo, questo interleaving di bit è denominato Morton code ed è un modo per combinare più dimensioni in una mentre si preserva la localizzazione dei punti.

Answer 2

Vorrei andare con un ciclo for e far funzionare l'algoritmo.

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

Una volta che il codice funziona correttamente, aumentare il livello di ottimizzazione. Il compilatore può eseguire alcune incredibili ottimizzazioni, come lo srotolamento del loop.

Puoi anche cercare sul Web "bit twiddling" e vedere se qualcuno di questi casi è come il tuo.

Answer 3

Ecco come lo farei ..

#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; 
} 

uscita:

a:  1010101111001101 
b:  0001001000110100 
merged: 10001001100011101010010110110010