In C / C ++ qual è il modo più semplice per invertire l’ordine dei bit in un byte?

Mentre ci sono diversi modi per invertire l’ordine dei bit in un byte, sono curioso di sapere qual è il “più semplice” da implementare per uno sviluppatore. E invertendo intendo:

1110 -> 0111 0010 -> 0100 

Questo è simile a, ma non un duplicato di questa domanda PHP.

Questo è simile a, ma non un duplicato di questa domanda. Questa domanda richiede il metodo più semplice da implementare da parte di uno sviluppatore. Il “Best Algorithm” riguarda la memoria e le prestazioni della CPU.

Se stai parlando di un singolo byte, una ricerca da tavolo è probabilmente la migliore, a meno che per qualche ragione non siano disponibili 256 byte.

Questo dovrebbe funzionare:

 unsigned char reverse(unsigned char b) { b = (b & 0xF0) >> 4 | (b & 0x0F) << 4; b = (b & 0xCC) >> 2 | (b & 0x33) << 2; b = (b & 0xAA) >> 1 | (b & 0x55) << 1; return b; } 

Prima i quattro bit di sinistra vengono scambiati con i quattro bit corretti. Quindi tutte le coppie adiacenti vengono scambiate e quindi tutti i bit singoli adiacenti. Ciò si traduce in un ordine inverso.

Penso che una tabella di ricerca debba essere uno dei metodi più semplici. Tuttavia, non è necessaria una tabella di ricerca completa.

 //Index 1==0b0001 => 0b1000 //Index 7==0b0111 => 0b1110 //etc static unsigned char lookup[16] = { 0x0, 0x8, 0x4, 0xc, 0x2, 0xa, 0x6, 0xe, 0x1, 0x9, 0x5, 0xd, 0x3, 0xb, 0x7, 0xf, }; uint8_t reverse(uint8_t n) { // Reverse the top and bottom nibble then swap them. return (lookup[n&0b1111] << 4) | lookup[n>>4]; } // Detailed breakdown of the math // + lookup reverse of bottom nibble // | + grab bottom nibble // | | + move bottom result into top nibble // | | | + combine the bottom and top results // | | | | + lookup reverse of top nibble // | | | | | + grab top nibble // VVVVVV // (lookup[n&0b1111] << 4) | lookup[n>>4] 

Questo è abbastanza semplice da codificare e verificare visivamente.
Alla fine, potrebbe anche essere più veloce di un tavolo completo. Il bit arith è economico e la tabella si adatta facilmente a una linea cache.

Vedi gli hack che girano un po ‘ per molte soluzioni. Copypasting da lì è ovviamente semplice da implementare. =)

Ad esempio (su una CPU a 32 bit):

 uint8_t b = byte_to_reverse; b = ((b * 0x0802LU & 0x22110LU) | (b * 0x8020LU & 0x88440LU)) * 0x10101LU >> 16; 

Se per “semplice implementazione” si intende qualcosa che può essere fatto senza un riferimento in un esame o colloquio di lavoro, allora la scommessa più sicura è probabilmente la copia inefficiente dei bit uno a uno in un’altra variabile in ordine inverso (già mostrato in altre risposte ).

Dal momento che nessuno ha pubblicato una soluzione di ricerca completa della tabella, ecco la mia:

 unsigned char reverse_byte(unsigned char x) { static const unsigned char table[] = { 0x00, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60, 0xe0, 0x10, 0x90, 0x50, 0xd0, 0x30, 0xb0, 0x70, 0xf0, 0x08, 0x88, 0x48, 0xc8, 0x28, 0xa8, 0x68, 0xe8, 0x18, 0x98, 0x58, 0xd8, 0x38, 0xb8, 0x78, 0xf8, 0x04, 0x84, 0x44, 0xc4, 0x24, 0xa4, 0x64, 0xe4, 0x14, 0x94, 0x54, 0xd4, 0x34, 0xb4, 0x74, 0xf4, 0x0c, 0x8c, 0x4c, 0xcc, 0x2c, 0xac, 0x6c, 0xec, 0x1c, 0x9c, 0x5c, 0xdc, 0x3c, 0xbc, 0x7c, 0xfc, 0x02, 0x82, 0x42, 0xc2, 0x22, 0xa2, 0x62, 0xe2, 0x12, 0x92, 0x52, 0xd2, 0x32, 0xb2, 0x72, 0xf2, 0x0a, 0x8a, 0x4a, 0xca, 0x2a, 0xaa, 0x6a, 0xea, 0x1a, 0x9a, 0x5a, 0xda, 0x3a, 0xba, 0x7a, 0xfa, 0x06, 0x86, 0x46, 0xc6, 0x26, 0xa6, 0x66, 0xe6, 0x16, 0x96, 0x56, 0xd6, 0x36, 0xb6, 0x76, 0xf6, 0x0e, 0x8e, 0x4e, 0xce, 0x2e, 0xae, 0x6e, 0xee, 0x1e, 0x9e, 0x5e, 0xde, 0x3e, 0xbe, 0x7e, 0xfe, 0x01, 0x81, 0x41, 0xc1, 0x21, 0xa1, 0x61, 0xe1, 0x11, 0x91, 0x51, 0xd1, 0x31, 0xb1, 0x71, 0xf1, 0x09, 0x89, 0x49, 0xc9, 0x29, 0xa9, 0x69, 0xe9, 0x19, 0x99, 0x59, 0xd9, 0x39, 0xb9, 0x79, 0xf9, 0x05, 0x85, 0x45, 0xc5, 0x25, 0xa5, 0x65, 0xe5, 0x15, 0x95, 0x55, 0xd5, 0x35, 0xb5, 0x75, 0xf5, 0x0d, 0x8d, 0x4d, 0xcd, 0x2d, 0xad, 0x6d, 0xed, 0x1d, 0x9d, 0x5d, 0xdd, 0x3d, 0xbd, 0x7d, 0xfd, 0x03, 0x83, 0x43, 0xc3, 0x23, 0xa3, 0x63, 0xe3, 0x13, 0x93, 0x53, 0xd3, 0x33, 0xb3, 0x73, 0xf3, 0x0b, 0x8b, 0x4b, 0xcb, 0x2b, 0xab, 0x6b, 0xeb, 0x1b, 0x9b, 0x5b, 0xdb, 0x3b, 0xbb, 0x7b, 0xfb, 0x07, 0x87, 0x47, 0xc7, 0x27, 0xa7, 0x67, 0xe7, 0x17, 0x97, 0x57, 0xd7, 0x37, 0xb7, 0x77, 0xf7, 0x0f, 0x8f, 0x4f, 0xcf, 0x2f, 0xaf, 0x6f, 0xef, 0x1f, 0x9f, 0x5f, 0xdf, 0x3f, 0xbf, 0x7f, 0xff, }; return table[x]; } 
 template  T reverse(T n, size_t b = sizeof(T) * CHAR_BIT) { assert(b <= std::numeric_limits::digits); T rv = 0; for (size_t i = 0; i < b; ++i, n >>= 1) { rv = (rv << 1) | (n & 0x01); } return rv; } 

MODIFICARE:

Convertito in un modello con il bitcount opzionale

Due linee:

 for(i=0;i<8;i++) reversed |= ((original>>i) & 0b1)<<(7-i); 

o in caso di problemi con la parte "0b1":

 for(i=0;i<8;i++) reversed |= ((original>>i) & 1)<<(7-i); 

"originale" è il byte che vuoi invertire. "invertito" è il risultato, inizializzato a 0.

Anche se probabilmente non è portatile, utilizzerei il linguaggio assembly.
Molti linguaggi di assemblaggio hanno istruzioni per ruotare un bit nel flag di carry e per ruotare il flag di carry nella parola (o byte).

L’algoritmo è:

 for each bit in the data type: rotate bit into carry flag rotate carry flag into destination. end-for 

Il codice del linguaggio di alto livello per questo è molto più complicato, perché C e C ++ non supportano la rotazione per trasportare e ruotare dal carry. La bandiera del carry deve essere modellata.

Modifica: linguaggio assembly, ad esempio

 ; Enter with value to reverse in R0. ; Assume 8 bits per byte and byte is the native processor type. LODI, R2 8 ; Set up the bit counter Loop: RRC, R0 ; Rotate R0 right into the carry bit. RLC, R1 ; Rotate R1 left, then append carry bit. DJNZ, R2 Loop ; Decrement R2 and jump if non-zero to "loop" LODR, R0 R1 ; Move result into R0. 

Il modo più semplice è probabilmente quello di scorrere le posizioni dei bit in un ciclo:

 unsigned char reverse(unsigned char c) { int shift; unsigned char result = 0; for (shift = 0; shift < CHAR_BIT; shift++) { if (c & (0x01 << shift)) result |= (0x80 >> shift); } return result; } 

Per l’input costante a 8 bit , questo non richiede memoria o CPU in fase di esecuzione:

 #define MSB2LSB(b) (((b)&1?128:0)|((b)&2?64:0)|((b)&4?32:0)|((b)&8?16:0)|((b)&16?8:0)|((b)&32?4:0)|((b)&64?2:0)|((b)&128?1:0)) 

L’ho usato per ARINC-429 dove l’ordine dei bit (endianness) dell’etichetta è opposto al resto della parola. L’etichetta è spesso una costante e convenzionalmente in ottale. Per esempio:

 #define LABEL_HF_COMM MSB2LSB(0205) 

Trovo la seguente soluzione più semplice dell’altro algoritmo di manipolazione di bit che ho visto qui.

 unsigned char reverse_byte(char a) { return ((a & 0x1) << 7) | ((a & 0x2) << 5) | ((a & 0x4) << 3) | ((a & 0x8) << 1) | ((a & 0x10) >> 1) | ((a & 0x20) >> 3) | ((a & 0x40) >> 5) | ((a & 0x80) >> 7); } 

Ottiene ogni bit nel byte e lo sposta di conseguenza, iniziando dal primo all’ultimo.

Spiegazione:

  ((a & 0x1) << 7) //get first bit on the right and shift it into the first left position | ((a & 0x2) << 5) //add it to the second bit and shift it into the second left position //and so on 

Potresti essere interessato a std::vector (che è bit-packed) e std::bitset

Dovrebbe essere il più semplice come richiesto.

 #include  #include  using namespace std; int main() { bitset<8> bs = 5; bitset<8> rev; for(int ii=0; ii!= bs.size(); ++ii) rev[bs.size()-ii-1] = bs[ii]; cerr << bs << " " << rev << endl; } 

Altre opzioni potrebbero essere più veloci.

EDIT: ti devo una soluzione usando std::vector

 #include  #include  #include  #include  using namespace std; int main() { vector b{0,0,0,0,0,1,0,1}; reverse(b.begin(), b.end()); copy(b.begin(), b.end(), ostream_iterator(cerr)); cerr << endl; } 

Il secondo esempio richiede l'estensione c ++ 0x (per inizializzare l'array con {...} ). Il vantaggio di usare un bitset o un file std::vector (o un boost::dynamic_bitset ) è che non si è limitati a byte o parole ma si può invertire un numero arbitrario di bit.

HTH

Ricerca tabella o

 uint8_t rev_byte(uint8_t x) { uint8_t y; uint8_t m = 1; while (m) { y >>= 1; if (m&x) { y |= 0x80; } m <<=1; } return y; } 

modificare

Guarda qui per altre soluzioni che potrebbero funzionare meglio per te

Prima di implementare qualsiasi soluzione algoritmica, controllare il linguaggio assembly per qualsiasi architettura della CPU che si sta utilizzando. La tua architettura potrebbe includere istruzioni che gestiscono manipolazioni bit a bit come questa (e cosa potrebbe essere più semplice di una singola istruzione di assemblaggio?).

Se tale istruzione non è disponibile, suggerirei di andare con il percorso della tabella di ricerca. Puoi scrivere uno script / programma per generare la tabella per te, e le operazioni di ricerca sarebbero più veloci di qualsiasi algoritmo di inversione di bit qui (al costo di dover memorizzare la tabella di ricerca da qualche parte).

un’implementazione più lenta ma più semplice:

 static int swap_bit(unsigned char unit) { /* * swap bit[7] and bit[0] */ unit = (((((unit & 0x80) >> 7) ^ (unit & 0x01)) << 7) | (unit & 0x7f)); unit = (((((unit & 0x80) >> 7) ^ (unit & 0x01))) | (unit & 0xfe)); unit = (((((unit & 0x80) >> 7) ^ (unit & 0x01)) << 7) | (unit & 0x7f)); /* * swap bit[6] and bit[1] */ unit = (((((unit & 0x40) >> 5) ^ (unit & 0x02)) << 5) | (unit & 0xbf)); unit = (((((unit & 0x40) >> 5) ^ (unit & 0x02))) | (unit & 0xfd)); unit = (((((unit & 0x40) >> 5) ^ (unit & 0x02)) << 5) | (unit & 0xbf)); /* * swap bit[5] and bit[2] */ unit = (((((unit & 0x20) >> 3) ^ (unit & 0x04)) << 3) | (unit & 0xdf)); unit = (((((unit & 0x20) >> 3) ^ (unit & 0x04))) | (unit & 0xfb)); unit = (((((unit & 0x20) >> 3) ^ (unit & 0x04)) << 3) | (unit & 0xdf)); /* * swap bit[4] and bit[3] */ unit = (((((unit & 0x10) >> 1) ^ (unit & 0x08)) << 1) | (unit & 0xef)); unit = (((((unit & 0x10) >> 1) ^ (unit & 0x08))) | (unit & 0xf7)); unit = (((((unit & 0x10) >> 1) ^ (unit & 0x08)) << 1) | (unit & 0xef)); return unit; } 

Può essere una soluzione veloce?

 int byte_to_be_reversed = ((byte_to_be_reversed>>7)&0x01)|((byte_to_be_reversed>>5)&0x02)| ((byte_to_be_reversed>>3)&0x04)|((byte_to_be_reversed>>1)&0x08)| ((byte_to_be_reversed<<7)&0x80)|((byte_to_be_reversed<<5)&0x40)| ((byte_to_be_reversed<<3)&0x20)|((byte_to_be_reversed<<1)&0x10); 

Elimina il trambusto dell'uso di un ciclo for! ma per favore dimmi se è efficiente e più veloce?

Questa semplice funzione utilizza una maschera per testare ogni bit nel byte di input e trasferirlo in un’uscita in movimento:

 char Reverse_Bits(char input) { char output = 0; for (unsigned char mask = 1; mask > 0; mask <<= 1) { output <<= 1; if (input & mask) output |= 1; } return output; } 

Questo è basato sull’unico BobStein-VisiBone fornito

 #define reverse_1byte(b) ( ((uint8_t)b & 0b00000001) ? 0b10000000 : 0 ) | \ ( ((uint8_t)b & 0b00000010) ? 0b01000000 : 0 ) | \ ( ((uint8_t)b & 0b00000100) ? 0b00100000 : 0 ) | \ ( ((uint8_t)b & 0b00001000) ? 0b00010000 : 0 ) | \ ( ((uint8_t)b & 0b00010000) ? 0b00001000 : 0 ) | \ ( ((uint8_t)b & 0b00100000) ? 0b00000100 : 0 ) | \ ( ((uint8_t)b & 0b01000000) ? 0b00000010 : 0 ) | \ ( ((uint8_t)b & 0b10000000) ? 0b00000001 : 0 ) 

Mi piace molto questo perché il compilatore gestisce automaticamente il lavoro per te, quindi non richiede ulteriori risorse.

questo può anche essere esteso a 16 bit …

 #define reverse_2byte(b) ( ((uint16_t)b & 0b0000000000000001) ? 0b1000000000000000 : 0 ) | \ ( ((uint16_t)b & 0b0000000000000010) ? 0b0100000000000000 : 0 ) | \ ( ((uint16_t)b & 0b0000000000000100) ? 0b0010000000000000 : 0 ) | \ ( ((uint16_t)b & 0b0000000000001000) ? 0b0001000000000000 : 0 ) | \ ( ((uint16_t)b & 0b0000000000010000) ? 0b0000100000000000 : 0 ) | \ ( ((uint16_t)b & 0b0000000000100000) ? 0b0000010000000000 : 0 ) | \ ( ((uint16_t)b & 0b0000000001000000) ? 0b0000001000000000 : 0 ) | \ ( ((uint16_t)b & 0b0000000010000000) ? 0b0000000100000000 : 0 ) | \ ( ((uint16_t)b & 0b0000000100000000) ? 0b0000000010000000 : 0 ) | \ ( ((uint16_t)b & 0b0000001000000000) ? 0b0000000001000000 : 0 ) | \ ( ((uint16_t)b & 0b0000010000000000) ? 0b0000000000100000 : 0 ) | \ ( ((uint16_t)b & 0b0000100000000000) ? 0b0000000000010000 : 0 ) | \ ( ((uint16_t)b & 0b0001000000000000) ? 0b0000000000001000 : 0 ) | \ ( ((uint16_t)b & 0b0010000000000000) ? 0b0000000000000100 : 0 ) | \ ( ((uint16_t)b & 0b0100000000000000) ? 0b0000000000000010 : 0 ) | \ ( ((uint16_t)b & 0b1000000000000000) ? 0b0000000000000001 : 0 ) 
 typedef struct { uint8_t b0:1; uint8_t b1:1; uint8_t b2:1; uint8_t b3:1; uint8_t b4:1; uint8_t b5:1; uint8_t b6:1; uint8_t b7:1; } bits_t; uint8_t reverse_bits(uint8_t src) { uint8_t dst = 0x0; bits_t *src_bits = (bits_t *)&src; bits_t *dst_bits = (bits_t *)&dst; dst_bits->b0 = src_bits->b7; dst_bits->b1 = src_bits->b6; dst_bits->b2 = src_bits->b5; dst_bits->b3 = src_bits->b4; dst_bits->b4 = src_bits->b3; dst_bits->b5 = src_bits->b2; dst_bits->b6 = src_bits->b1; dst_bits->b7 = src_bits->b0; return dst; } 
 #include  #include  int main() { int i; unsigned char rev = 0x70 ; // 0b01110000 unsigned char tmp = 0; for(i=0;i<8;i++) { tmp |= ( ((rev & (1< 
 #define BITS_SIZE 8 int reverseBits ( int a ) { int rev = 0; int i; /* scans each bit of the input number*/ for ( i = 0; i < BITS_SIZE - 1; i++ ) { /* checks if the bit is 1 */ if ( a & ( 1 << i ) ) { /* shifts the bit 1, starting from the MSB to LSB * to build the reverse number */ rev |= 1 << ( BITS_SIZE - 1 ) - i; } } return rev; } 
  xor ax,ax xor bx,bx mov cx,8 mov al,original_byte! cycle: shr al,1 jnc not_inc inc bl not_inc: test cx,cx jz,end_cycle shl bl,1 loop cycle end_cycle: 

il byte invertito sarà al registro bl

Questa è una vecchia domanda, ma nessuno sembra aver mostrato il modo semplice e chiaro (il più vicino è stato edW). Ho usato C # (e il meraviglioso LinqPad per testarlo) ma non c’è nulla in questo esempio che non possa essere fatto facilmente in C.

Incolla quanto segue nel meraviglioso LinqPad ( https://www.linqpad.net/ ), (che è dove ho provato questo):

 void PrintBinary(string prompt, int num, int pad = 8) { Debug.WriteLine($"{prompt}: {Convert.ToString(num, 2).PadLeft(pad, '0')}"); } int ReverseBits(int num) { int result = 0; int saveBits = num; for (int i = 1; i <= 8; i++) { // Move the result one bit to the left result = result << 1; //PrintBinary("saveBits", saveBits); // Extract the right-most bit var nextBit = saveBits & 1; //PrintBinary("nextBit", nextBit, 1); // Add our extracted bit to the result result = result | nextBit; //PrintBinary("result", result); // We're done with that bit, rotate it off the right saveBits = saveBits >> 1; //Debug.WriteLine(""); } return result; } void PrintTest(int nextNumber) { var result = ReverseBits(nextNumber); Debug.WriteLine("---------------------------------------"); PrintBinary("Original", nextNumber); PrintBinary("Reverse", result); } void Main() { // Calculate the reverse for each number between 1 and 255 for (int x = 250; x < 256; x++) PrintTest(x); } 

Che ne dici di questo …

 int value = 0xFACE; value = ((0xFF & value << 8) | (val >> 8); 

Che ne dici di XOR solo il byte con 0xFF.

unsigned char reverse(unsigned char b) { b ^= 0xFF; return b; }