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

110

Si bien hay varias formas de invertir el orden de los bits en un byte, tengo curiosidad por saber cuál es la "más simple" de implementar para un desarrollador. Y al revertir quiero decir:

1110 -> 0111
0010 -> 0100

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

Esto es similar, pero no un duplicado de esta pregunta C. Esta pregunta solicita el método más fácil de implementar por parte de un desarrollador. El "Mejor algoritmo" se ocupa de la memoria y el rendimiento de la CPU.

nathan
fuente
Utilice ensamblaje en línea. Mejor, coloque la función en una unidad de traducción separada. Tenga un módulo de lenguaje ensamblador para cada plataforma de destino. Dejemos que el proceso de construcción elija los módulos.
Thomas Matthews
@Andreas Implementación más simple
nathan

Respuestas:

102

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.

e.James
fuente
12
Si estamos hablando de algo que es simple de implementar sin copiar una solución lista para usar, crear la tabla de búsqueda aún requiere otra solución. (Por supuesto, uno podría hacerlo a mano, pero eso es propenso a errores y requiere mucho tiempo…)
Arkku
7
Puede comprimir la matriz en algo menos de 256 bytes si ignora los palíndromos.
wilhelmtell
8
@wilhelmtell: necesitaría una tabla para saber cuáles son los palíndromos.
Mark Ransom
6
@wilhelmtell: Bueno, para escribir el script, todavía se necesita otra solución, que era mi punto: una tabla de búsqueda es simple de usar pero no simple de crear. (Excepto copiando una tabla de búsqueda ya preparada, pero también podría copiar cualquier solución). Por ejemplo, si la solución "más simple" se considera una que podría escribirse en papel en un examen o entrevista, no lo haría comenzar a hacer una tabla de búsqueda a mano y hacer que el programa para hacerlo ya incluiría una solución diferente (que sería más simple por sí sola que la que incluye tanto a ella como a la tabla).
Arkku
4
@Arkku, lo que quise decir es escribir un script que genere la tabla de los primeros 256 bytes y su mapeo inverso. Sí, ha vuelto a escribir la función inversa, pero ahora en su lenguaje de secuencias de comandos favorito, y puede ser tan desagradable como desee; la va a tirar tan pronto como esté lista y la haya ejecutado una vez. Tener la salida del script como código C, incluso: unsigned int rtable[] = {0x800, 0x4000, ...};. Luego, deseche el guión y olvídese de que lo tuvo. Es mucho más rápido de escribir que el código C ++ equivalente, y solo se ejecutará una vez, por lo que obtienes tiempo de ejecución O (1) en tu código C ++.
wilhelmtell
227

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, se intercambian todos los pares adyacentes y luego todos los bits individuales adyacentes. Esto da como resultado un orden inverso.

algo
fuente
26
Razonablemente corto y rápido, pero no simple.
Mark Ransom
3
Este enfoque también se generaliza limpiamente para realizar el intercambio de bytes por endianidad.
Boojum
2
No es el enfoque más simple, pero me gusta +1.
Nathan
7
Si, es simple. Es una especie de algoritmo de divide y vencerás. ¡Excelente!
kiewic
¿Es más rápido que el método sugerido por @Arkku a continuación?
qed
122

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 mesa completa. El arit de bits es barato y la tabla cabe fácilmente en una línea de caché.

deft_code
fuente
10
Esa es una excelente manera de reducir la complejidad de la solución de mesa. +1
e.James
3
Agradable, pero te hará perder un caché.
Johan Kotlinski
7
@kotlinski: ¿qué provocará una falta de caché? Creo que la versión de tabla pequeña puede ser más eficiente en caché que la grande. En mi Core2, una línea de caché tiene 64 bytes de ancho, la tabla completa abarcaría varias líneas, mientras que la tabla más pequeña se ajusta fácilmente a una sola línea.
deft_code
4
@kotlinski: la localidad temporal es más importante para los aciertos de caché o las estrategias de reemplazo que la localidad de la dirección
cfi
6
@Harshdeep: considere los índices codificados en binario de las entradas de la tabla. índice b0000 (0) -> b0000 (0x0) aburrido; b0001(1) -> b1000(0x8), b0010(2) -> b0100(0x4), b1010(10) -> b0101(0x5). ¿Ves el patrón? Es lo suficientemente simple como para que pueda calcularlo en su cabeza (si puede leer binario, de lo contrario necesitará papel para resolverlo). En cuanto al salto, invertir un entero de 8 bits es lo mismo que invertir partes de 4 bits y luego intercambiarlas; Reclamo experiencia e intuición (o magia).
deft_code
46

Vea los trucos de juguete para muchas soluciones. Copiar desde allí es obviamente fácil 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 se puede hacer 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 ).

Arkku
fuente
1
Desde su URL: CPU de 32 bits: b = ((b * 0x0802LU & 0x22110LU) | (b * 0x8020LU & 0x88440LU)) * 0x10101LU >> 16;
Joshua
1
@ Joshua: Ese también es mi favorito personal. La advertencia (como se indica en la página vinculada) es que debe asignarse o convertirse en un uint8_t o habrá basura en los bits superiores.
Arkku
41

Como nadie publicó una solución completa de búsqueda de tablas, aquí está la mía:

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];
}
fredoverflow
fuente
2
Útil, gracias. Parece que mi método de cambio más lento estaba limitando el rendimiento en una aplicación integrada. Tabla colocada en ROM en un PIC (con la adición de la palabra clave rom).
flend el
25
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:

Convertido en una plantilla con el bitcount opcional

y y
fuente
@nvl - arreglado. Empecé a construir como una plantilla, pero decidió a mitad de no hacerlo ... demasiados & gt & lt
andand
Para mayor pedenatría, reemplace sizeof(T)*8con sizeof(T)*CHAR_BITS.
Pillsy
6
@andand Para obtener más pendiente, reemplácelo sizeof(T)*CHAR_BITpor std::numeric_limits<T>::digits(casi 4 años de pedantería más tarde).
Morwenn
1
Debería ser CHAR_BIT, no CHAR_BITS.
Xunie
1
debería ser rv = (rv << 1) | (n & 0x01);
Vignesh
16

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 invertir. "invertido" es el resultado, inicializado a 0.

Daniel
fuente
14

Aunque probablemente no sea portátil, usaría lenguaje ensamblador.
Muchos lenguajes ensambladores 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 admiten rotar para llevar y rotar desde llevar. 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.
Thomas Matthews
fuente
7
Creo que esta respuesta es lo opuesto a simple. No portátil, ensamblador y lo suficientemente complejo como para escribirse en pseudocódigo en lugar del ensamblado real.
deft_code
3
Es muy sencillo. Lo puse en pseudocódigo porque los mnemónicos de ensamblaje son específicos de una clase de procesador y hay muchas razas por ahí. Si lo desea, puedo editar esto para mostrar el lenguaje ensamblador simple.
Thomas Matthews
Se podría ver si la optimización de un compilador se simplifica en una instrucción de ensamblaje adecuada.
Sparky
12

Encuentro la siguiente solución más simple que los otros algoritmos de manipulación de bits 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);
}

Obtiene cada bit del 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
dau_sama
fuente
¡Hermoso! Mi favorito hasta ahora.
Nick Rameau
Esto es ciertamente simple, pero debe señalarse que el tiempo de ejecución es O (n) en lugar de O (log₂ n), donde n es el número de bits (8, 16, 32, 64, etc.).
Todd Lehman
10

La forma más sencilla es probablemente iterar sobre las posiciones de los bits 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;
}
algo
fuente
es CHAR_BIT, sin 's'
ljrk
¿Por qué usarlo CHAR_BITcuando asume charque tiene 8 bits?
chqrlie
6

Para el caso muy limitado de entrada constante de 8 bits , este método no cuesta memoria ni 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 (endianidad) de la etiqueta es opuesto al resto de la palabra. La etiqueta es a menudo una constante y convencionalmente en octal.

Así es como lo usé para definir una constante, porque la especificación define esta etiqueta como big-endian 205 octal.

#define LABEL_HF_COMM MSB2LSB(0205)

Más ejemplos:

assert(0b00000000 == MSB2LSB(0b00000000));
assert(0b10000000 == MSB2LSB(0b00000001));
assert(0b11000000 == MSB2LSB(0b00000011));
assert(0b11100000 == MSB2LSB(0b00000111));
assert(0b11110000 == MSB2LSB(0b00001111));
assert(0b11111000 == MSB2LSB(0b00011111));
assert(0b11111100 == MSB2LSB(0b00111111));
assert(0b11111110 == MSB2LSB(0b01111111));
assert(0b11111111 == MSB2LSB(0b11111111));
assert(0b10101010 == MSB2LSB(0b01010101));
Bob Stein
fuente
5

Puede estar interesado en std::vector<bool>(que está empaquetado en bits) ystd::bitset

Debe ser el más simple que se solicite.

#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 la extensión c ++ 0x (para inicializar la matriz {...}). La ventaja de usar a bitseto a std::vector<bool>(o a boost::dynamic_bitset) es que no está limitado a bytes o palabras, sino que puede invertir un número arbitrario de bits.

HTH

baol
fuente
¿Cómo es el bitset más simple que un pod aquí? Muestra el código o no lo es.
wilhelmtell
En realidad, creo que el código revertirá el conjunto de bits y luego lo revertirá a su original. Cambiar ii! = Tamaño (); a ii <tamaño () / 2; y hará un mejor trabajo =)
Viktor Sehr
(@ viktor-sehr no, no lo hará, rev es diferente de bs). De todos modos, no me gusta la respuesta a mí mismo: creo que este es un caso en el que la aritmética binaria y los operadores de desplazamiento son más adecuados. Sigue siendo el más sencillo de entender.
baol
¿Qué tal si std::vector<bool> b = { ... }; std::vector<bool> rb ( b.rbegin(), b.rend()); utilizamos iteradores inversos directamente?
MSalters
@MSalters Me gusta la inmutabilidad de la misma.
baol
5

Hay muchas formas de invertir bits dependiendo de lo que quiera decir con la "forma más sencilla".


Invertir por rotación

Probablemente el más lógico, consiste en rotar el byte aplicando una máscara en el primer bit (n & 1):

unsigned char reverse_bits(unsigned char b)
{
    unsigned char   r = 0;
    unsigned        byte_len = 8;

    while (byte_len--) {
        r = (r << 1) | (b & 1);
        b >>= 1;
    }
    return r;
}

1) Como la longitud de un carácter sin firma es de 1 byte, que es igual a 8 bits, significa que escanearemos cada bit while (byte_len--)

2) Primero verificamos si b está un poco en el extremo derecho con (b & 1); si es así, establecemos el bit 1 en r con |y lo movemos solo 1 bit a la izquierda multiplicando r por 2 con(r << 1)

3) Luego dividimos nuestro carácter b sin signo por 2 con b >>=1para borrar el bit ubicado en el extremo derecho de la variable b. Como recordatorio, b >> = 1; es equivalente a b / = 2;


Reverso en una línea

Esta solución se atribuye a Rich Schroeppel en la sección Programming Hacks

unsigned char reverse_bits3(unsigned char b)
{
    return (b * 0x0202020202ULL & 0x010884422010ULL) % 0x3ff;
}

1) La operación de multiplicación (b * 0x0202020202ULL) crea cinco copias separadas del patrón de bytes de 8 bits para distribuirlas en un valor de 64 bits.

2) La operación AND (& 0x010884422010ULL) selecciona los bits que están en las posiciones correctas (invertidas), en relación con cada grupo de bits de 10 bits.

3) Juntas, las operaciones de multiplicación y Y copian los bits del byte original para que aparezcan en solo uno de los conjuntos de 10 bits. Las posiciones invertidas de los bits del byte original coinciden con sus posiciones relativas dentro de cualquier conjunto de 10 bits.

4) El último paso (% 0x3ff), que implica la división del módulo por 2 ^ 10 - 1, tiene el efecto de fusionar cada conjunto de 10 bits (desde las posiciones 0-9, 10-19, 20-29, ...) en el valor de 64 bits. No se superponen, por lo que los pasos de suma subyacentes a la división del módulo se comportan como operaciones OR.


Solución de dividir y conquistar

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

Esta es la respuesta más votada y, a pesar de algunas explicaciones, creo que para la mayoría de las personas se siente difícil visualizar lo que realmente significan 0xF0, 0xCC, 0xAA, 0x0F, 0x33 y 0x55.

No aprovecha '0b', que es una extensión de GCC y se incluye desde el estándar C ++ 14, lanzado en diciembre de 2014, así que un tiempo después de esta respuesta que data de abril de 2010

Las constantes enteras se pueden escribir como constantes binarias, que consisten en una secuencia de dígitos '0' y '1', precedidos por '0b' o '0B'. Esto es particularmente útil en entornos que operan mucho a nivel de bits (como microcontroladores).

Consulte los siguientes fragmentos de código para recordar y comprender aún mejor esta solución en la que nos movemos mitad a mitad:

unsigned char reverse(unsigned char b) {
   b = (b & 0b11110000) >> 4 | (b & 0b00001111) << 4;
   b = (b & 0b11001100) >> 2 | (b & 0b00110011) << 2;
   b = (b & 0b10101010) >> 1 | (b & 0b01010101) << 1;
   return b;
}

NB: Esto >> 4se debe a que hay 8 bits en 1 byte, que es un carácter sin signo, por lo que queremos tomar la otra mitad, y así sucesivamente.

Podríamos aplicar fácilmente esta solución a 4 bytes con solo dos líneas adicionales y siguiendo la misma lógica. Dado que ambas máscaras se complementan, incluso podemos usar ~ para cambiar bits y ahorrar algo de tinta:

uint32_t reverse_integer_bits(uint32_t b) {
   uint32_t mask = 0b11111111111111110000000000000000;
   b = (b & mask) >> 16 | (b & ~mask) << 16;
   mask = 0b11111111000000001111111100000000;
   b = (b & mask) >> 8 | (b & ~mask) << 8;
   mask = 0b11110000111100001111000011110000;
   b = (b & mask) >> 4 | (b & ~mask) << 4;
   mask = 0b11001100110011001100110011001100;
   b = (b & mask) >> 2 | (b & ~mask) << 2;
   mask = 0b10101010101010101010101010101010;
   b = (b & mask) >> 1 | (b & ~mask) << 1;
   return b;
}

[Solo C ++] Revertir cualquier sin firmar (plantilla)

La lógica anterior se puede resumir con un bucle que funcionaría en cualquier tipo de sin firmar:

template <class T>
T reverse_bits(T n) {
    short bits = sizeof(n) * 8; 
    T mask = ~T(0); // equivalent to uint32_t mask = 0b11111111111111111111111111111111;

    while (bits >>= 1) {
        mask ^= mask << (bits); // will convert mask to 0b00000000000000001111111111111111;
        n = (n & ~mask) >> bits | (n & mask) << bits; // divide and conquer
    }

    return n;
}

Pruébelo usted mismo con la inclusión de la función anterior:

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

template <class T>
void print_binary(T n)
{   T mask = 1ULL << ((sizeof(n) * 8) - 1);  // will set the most significant bit
    for(; mask != 0; mask >>= 1) putchar('0' | !!(n & mask));
    putchar('\n');
}

int main() {
    uint32_t n = 12;
    print_binary(n);
    n = reverse_bits(n); 
    print_binary(n);
    unsigned char c = 'a';
    print_binary(c);
    c = reverse_bits(c);
    print_binary(c);
    uint16_t s = 12;
    print_binary(s);
    s = reverse_bits(s);
    print_binary(s);
    uint64_t l = 12;
    print_binary(l);
    l = reverse_bits(l);
    print_binary(l);
    return 0;
}

Invertir con asm volátil

Por último, pero no menos importante, si lo más simple significa menos líneas, ¿por qué no intentar el ensamblaje en línea?

Puede probar el siguiente fragmento de código agregando -masm=intelal compilar:

unsigned char reverse_bits(unsigned char c) {
    __asm__ __volatile__ (R"(
        mov cx, 8       
    daloop:                   
        ror di          
        adc ax, ax      
        dec cx          
        jnz short daloop  
    ;)");
}

Explicaciones línea por línea:

        mov cx, 8       ; we will reverse the 8 bits contained in one byte
    daloop:             ; while loop
        shr di          ; Shift Register `di` (containing value of the first argument of callee function) to the Right
        rcl ax          ; Rotate Carry Left: rotate ax left and add the carry from shr di, the carry is equal to 1 if one bit was "lost" from previous operation 
        dec cl          ; Decrement cx
        jnz short daloop; Jump if cx register is Not equal to Zero, else end loop and return value contained in ax register
Antonin GAVREL
fuente
3

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

nategoose
fuente
3

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;
}
Wenlujón
fuente
3

¿Puede ser esta una solución rápida?

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

¡Se deshace del ajetreo de usar un bucle for! pero expertos, por favor, díganme si esto es eficiente y rápido.

Francachela
fuente
Este tiempo de ejecución es O (n) en lugar de O (log₂ n), donde n es el número de bits (8, 16, 32, 64, etc.). Consulte en otra parte las respuestas que se ejecutan en tiempo O (log₂ n).
Todd Lehman
2

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

Si tal instrucción no está disponible, sugeriría seguir la ruta de la tabla de búsqueda. Puede escribir un script / programa para generar la tabla por 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).

bta
fuente
2

Esta función simple usa una máscara para probar cada bit en el byte de entrada y transferirlo a una salida cambiante:

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;
}
luci88filter
fuente
La máscara debe estar sin firmar, lo siento.
luci88filter
1

Éste se basa en el proporcionado por 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 este porque el compilador maneja automáticamente el trabajo por usted, por lo que 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 ) 
Natthapol Vanasrivilai
fuente
Lo pondría bentre paréntesis en caso de que sea una expresión más compleja que un solo número, y tal vez también cambie el nombre de la macro REVERSE_BYTEcomo una pista de que probablemente no desee tener una expresión más compleja (tiempo de ejecución) allí. O conviértalo en una función en línea. (Pero en general, me gusta esto por ser lo suficientemente simple como para que pueda hacerlo desde la memoria fácilmente con muy pocas posibilidades de error).
Arkku
1

Suponiendo que su compilador permita unsigned long long :

unsigned char reverse(unsigned char b) {
  return (b * 0x0202020202ULL & 0x010884422010ULL) % 1023;
}

Descubierto aquí

mascIT
fuente
1

Si utiliza un microcontrolador pequeño y necesita una solución de alta velocidad con un tamaño reducido, esto podría ser una solución. Es posible usarlo para un proyecto C, pero necesita agregar este archivo como archivo ensamblador * .asm, a su proyecto C. Instrucciones: En el proyecto C, agregue esta declaración:

extern uint8_t byte_mirror(uint8_t);

Llame a esta función desde C

byteOutput= byte_mirror(byteInput);

Este es el código, solo es adecuado para 8051 core. En el registro de la CPU, r0 hay datos de byteInput . El código gire a la derecha r0 cross carry y luego gire a la izquierda a r1 . Repita este procedimiento 8 veces, por cada bit. Luego, el registro r1 se devuelve a la función c como byteOutput. En el núcleo 8051 solo es posible rotar el acumulador a .

NAME     BYTE_MIRROR
RSEG     RCODE
PUBLIC   byte_mirror              //8051 core        

byte_mirror
    mov r3,#8;
loop:   
    mov a,r0;
    rrc a;
    mov r0,a;    
    mov a,r1;
    rlc a;   
    mov r1,a;
    djnz r3,loop
    mov r0,a
    ret

PROS: Ocupa poco espacio, es de alta velocidad CONTRAS: No es código reutilizable, es solo para 8051

011101101-> llevar

101101110 <-cargar

Josko Marsic
fuente
Si bien este código puede responder a la pregunta, sería mejor incluir algo de contexto, explicando cómo funciona y cuándo usarlo. Las respuestas de solo código no son útiles a largo plazo.
fNek
0
  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 el registro bl

asm_fan
fuente
3
En otro contexto, esa puede ser una respuesta justa, pero la pregunta era sobre C o C ++, no sobre asm ...
jadsq
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;
}
Colmillo Tai-Yuan
fuente
Como nota de estilo, encuentro el uso de uint8_tpara los campos de 1 bit un poco feo, ya que parece decir primero que tomará 8 bits pero luego al final de la línea lo define como un solo bit. Me gustaría utilizar unsigned b0:1etc
Arkku
0
#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;
}
AHMED ANWAR
fuente
Por favor agregue alguna explicación.
zcui93
0

Creo que esto es bastante simple

uint8_t reverse(uint8_t a)
{
  unsigned w = ((a << 7) & 0x0880) | ((a << 5) & 0x0440) | ((a << 3) & 0x0220) | ((a << 1) & 0x0110);
  return static_cast<uint8_t>(w | (w>>8));
}

o

uint8_t reverse(uint8_t a)
{
  unsigned w = ((a & 0x11) << 7) | ((a & 0x22) << 5) | ((a & 0x44) << 3) | ((a & 0x88) << 1);
  return static_cast<uint8_t>(w | (w>>8));
}
Agbinfo
fuente
0
unsigned char c ; // the original
unsigned char u = // the reversed
c>>7&0b00000001 |
c<<7&0b10000000 |
c>>5&0b00000010 |
c<<5&0b01000000 |
c>>3&0b00000100 |
c<<3&0b00100000 |
c>>1&0b00001000 |
c<<1&0b00010000 ;

Explanation: exchanged bits as per the arrows below.
01234567
<------>
#<---->#
##<-->##
###<>###
Mahen
fuente
0

Incluiré mi solución, ya que hasta ahora no puedo encontrar nada como esto en las respuestas. Quizás esté un poco sobre-diseñado, pero genera la tabla de búsqueda usando C ++ 14 std::index_sequenceen tiempo de compilación.

#include <array>
#include <utility>

constexpr unsigned long reverse(uint8_t value) {
    uint8_t result = 0;
    for (std::size_t i = 0, j = 7; i < 8; ++i, --j) {
        result |= ((value & (1 << j)) >> j) << i;
    }
    return result;
}

template<size_t... I>
constexpr auto make_lookup_table(std::index_sequence<I...>)
{
    return std::array<uint8_t, sizeof...(I)>{reverse(I)...};   
}

template<typename Indices = std::make_index_sequence<256>>
constexpr auto bit_reverse_lookup_table()
{
    return make_lookup_table(Indices{});
}

constexpr auto lookup = bit_reverse_lookup_table();

int main(int argc)
{
    return lookup[argc];
}

https://godbolt.org/z/cSuWhF

K. Kirsz
fuente
0

Aquí hay una solución simple y legible, portátil para todas las plataformas compatibles, incluidas aquellas con sizeof(char) == sizeof(int):

#include <limits.h>

unsigned char reverse(unsigned char c) {
    int shift;
    unsigned char result = 0;

    for (shift = 0; shift < CHAR_BIT; shift++) {
        result <<= 1;
        result |= c & 1;
        c >>= 1;
    }
    return result;
}
chqrlie
fuente
0

Sé que esta pregunta está fechada, pero sigo pensando que el tema es relevante para algunos propósitos, y aquí hay una versión que funciona muy bien y es legible. No puedo decir que sea el más rápido o el más eficiente, pero debería ser uno de los más limpios. También he incluido una función auxiliar para mostrar fácilmente los patrones de bits. Esta función usa algunas de las funciones de la biblioteca estándar en lugar de escribir su propio manipulador de bits.

#include <algorithm>
#include <bitset>
#include <exception>
#include <iostream>
#include <limits>
#include <string>

// helper lambda function template
template<typename T>
auto getBits = [](T value) {
    return std::bitset<sizeof(T) * CHAR_BIT>{value};
};

// Function template to flip the bits
// This will work on integral types such as int, unsigned int,
// std::uint8_t, 16_t etc. I did not test this with floating
// point types. I chose to use the `bitset` here to convert
// from T to string as I find it easier to use than some of the
// string to type or type to string conversion functions,
// especially when the bitset has a function to return a string. 
template<typename T>
T reverseBits(T& value) {
    static constexpr std::uint16_t bit_count = sizeof(T) * CHAR_BIT;

    // Do not use the helper function in this function!
    auto bits = std::bitset<bit_count>{value};
    auto str = bits.to_string();
    std::reverse(str.begin(), str.end());
    bits = std::bitset<bit_count>(str);
    return static_cast<T>( bits.to_ullong() );
}

// main program
int main() {
    try {
        std::uint8_t value = 0xE0; // 1110 0000;
        std::cout << +value << '\n'; // don't forget to promote unsigned char
        // Here is where I use the helper function to display the bit pattern
        auto bits = getBits<std::uint8_t>(value);
        std::cout << bits.to_string() << '\n';

        value = reverseBits(value);
        std::cout << +value << '\n'; // + for integer promotion

        // using helper function again...
        bits = getBits<std::uint8_t>(value);
        std::cout << bits.to_string() << '\n';

    } catch(const std::exception& e) {  
        std::cerr << e.what();
        return EXIT_FAILURE;
    }
    return EXIT_SUCCESS;
}

Y da el siguiente resultado.

224
11100000
7
00000111
Francis Cugler
fuente
0

Este me ayudó con el conjunto de matrices de matriz de puntos de 8x8.

uint8_t mirror_bits(uint8_t var)
{
    uint8_t temp = 0;
    if ((var & 0x01))temp |= 0x80;
    if ((var & 0x02))temp |= 0x40;
    if ((var & 0x04))temp |= 0x20;
    if ((var & 0x08))temp |= 0x10;

    if ((var & 0x10))temp |= 0x08;
    if ((var & 0x20))temp |= 0x04;
    if ((var & 0x40))temp |= 0x02;
    if ((var & 0x80))temp |= 0x01;

    return temp;
}
R1S8K
fuente
1
Esta función no funciona realmente, el reverso de 0b11001111 debería ser 0b11110011, pero falla con esta función. El mismo método de prueba funciona para muchas de las otras funciones enumeradas aquí.
Dan
Sí, gracias, corregí mi respuesta. Gracias por
informarme