kilobyte - En C/C++, ¿cuál es la forma más sencilla de invertir el orden de los bits en un byte?

que es un bit (25)

¿Puede ser esta solución rápida?

¡Se deshace del ajetreo de usar un bucle for! pero los expertos me dicen si esto es eficiente y más rápido?

Si bien hay varias formas de invertir el orden de los bits en un byte, tengo curiosidad por saber qué es lo "más simple" que puede implementar un desarrollador. Y al revertir quiero decir:

1110 -> 0111 0010 -> 0100

Esto es similar a, pero no es un duplicado de this pregunta PHP.

Esto es similar a, pero no es un duplicado de this pregunta C. Esta pregunta está pidiendo el método más fácil de implementar por un desarrollador. El "Mejor Algoritmo" se refiere a la memoria y el rendimiento de la CPU.

¿Qué tal solo XOR el byte con 0xFF?

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

Antes de implementar cualquier solución algorítmica, verifique el lenguaje ensamblador para la arquitectura de CPU que esté utilizando. Su arquitectura puede incluir instrucciones que manejen manipulaciones bit a bit como esta (¿y qué podría ser más simple que una instrucción de ensamblaje única?).

Si tal instrucción no está disponible, entonces sugeriría ir con la ruta de la tabla de búsqueda. Puede escribir un script / programa para generar la tabla para usted, y las operaciones de búsqueda serían más rápidas que cualquiera de los algoritmos de inversión de bits aquí (a costa de tener que almacenar la tabla de búsqueda en algún lugar).

Aunque probablemente no sea portátil, usaría el lenguaje ensamblador.
Muchos lenguajes ensamblados tienen instrucciones para rotar un poco en la bandera de acarreo y para rotar la bandera de acarreo en la palabra (o byte).

El algoritmo es:

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

El código de lenguaje de alto nivel para esto es mucho más complicado, porque C y C ++ no son compatibles con la rotación para transportar y girar desde el transporte. La bandera de acarreo tiene que modelarse.

Editar: lenguaje ensamblador, por ejemplo

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

Búsqueda de tabla 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; }

editar

Busque aquí otras soluciones que podrían funcionar mejor para usted

Como nadie publicó una solución de búsqueda de tabla completa, aquí está el mío:

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

Creo que una tabla de búsqueda tiene que ser uno de los métodos más simples. Sin embargo, no necesita una tabla de búsqueda 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 // V V V V V V // (lookup[n&0b1111] << 4) | lookup[n>>4]

Esto es bastante simple de codificar y verificar visualmente.
En última instancia, esto podría ser incluso más rápido que una tabla completa. El bit arith es barato y la tabla encaja fácilmente en una línea de caché.

Dos lineas:

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

o en caso de que tenga problemas con la parte "0b1":

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

"original" es el byte que desea revertir. "invertido" es el resultado inicializado en 0.

Encuentro la siguiente solución más simple que los otros algoritmos de violín que he visto aquí.

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

Se pone cada bit en el byte y lo desplaza en consecuencia, comenzando desde el primero hasta el último.

Explicación:

((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

Esta es una vieja pregunta, pero nadie parece haber mostrado la manera fácil y clara (la más cercana fue EDW). LinqPad C # (y el maravilloso LinqPad para probar esto) pero no hay nada en este ejemplo que no se pueda hacer fácilmente en C.

Pegue lo siguiente en el maravilloso LinqPad ( LinqPad ), (que es donde probé esto):

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

Esta sencilla función utiliza una máscara para probar cada bit en el byte de entrada y transferirlo a un resultado de desplazamiento:

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

Este se basa en el que proporcionó BobStein-VisiBone

#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 )

Realmente me gusta mucho porque el compilador maneja automáticamente el trabajo por usted, por lo tanto no requiere más recursos.

esto también se puede extender a 16 bits ...

#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 )

Esto debería funcionar:

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

Primero, los cuatro bits de la izquierda se intercambian con los cuatro bits de la derecha. Luego, todos los pares adyacentes se intercambian y luego todos los bits individuales adyacentes. Esto da como resultado un orden inverso.

La forma más simple es, probablemente, iterar sobre las posiciones de bit en un bucle:

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

Para una entrada constante de 8 bits , esto no cuesta memoria o CPU en tiempo de ejecución:

#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))

Usé esto para ARINC-429 donde el orden de bits (endianness) de la etiqueta es opuesto al resto de la palabra. La etiqueta es a menudo una constante, y convencionalmente en octal. Por ejemplo:

#define LABEL_HF_COMM MSB2LSB(0205)

Puede estar interesado en std::vector<bool> (que está lleno de bits) y std::bitset

Debería ser el más simple según lo solicitado.

#include <iostream> #include <bitset> 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; }

Otras opciones pueden ser más rápidas.

EDITAR: Te debo una solución usando std::vector<bool>

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

El segundo ejemplo requiere una extensión c ++ 0x (para inicializar la matriz con {...} ). La ventaja de utilizar un conjunto de bitset o un std::vector<bool> (o un boost::dynamic_bitset ) es que no está limitado a bytes o palabras, sino que puede revertir un número arbitrario de bits.

HTH

Que tal este...

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

Si está hablando de un solo byte, una búsqueda de tabla es probablemente la mejor opción, a menos que por alguna razón no tenga 256 bytes disponibles.

Vea los hackers que hacen trizas para muchas soluciones. Copiar desde allí es obviamente simple de implementar. =)

Por ejemplo (en una CPU de 32 bits):

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

Si por "simple de implementar" uno significa algo que puede hacerse sin una referencia en un examen o entrevista de trabajo, entonces la apuesta más segura es probablemente la copia ineficiente de bits uno por uno en otra variable en orden inverso (ya se muestra en otras respuestas )

una implementación más lenta pero más simple:

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

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:

el byte invertido estará en bl register

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

#include <stdio.h> #include <stdlib.h> int main() { int i; unsigned char rev = 0x70 ; // 0b01110000 unsigned char tmp = 0; for(i=0;i<8;i++) { tmp |= ( ((rev & (1<<i))?1:0) << (7-i)); } rev = tmp; printf("%x", rev); //0b00001110 binary value of given number return 0; }

template <typename T> T reverse(T n, size_t b = sizeof(T) * CHAR_BIT) { assert(b <= std::numeric_limits<T>::digits); T rv = 0; for (size_t i = 0; i < b; ++i, n >>= 1) { rv = (rv << 1) | (n & 0x01); } return rv; }

EDITAR:

Se convirtió a una plantilla con el bitcount opcional

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