Inversión de bits de un número entero, ignorando el tamaño del entero y el endianidad
https://stackoverflow.com/questions/63776
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Dado un tipo de definición entero:
typedef unsigned int TYPE;
o
typedef unsigned long TYPE;
Tengo el siguiente código para invertir los bits de un número entero:
TYPE max_bit= (TYPE)-1;
void reverse_int_setup()
{
TYPE bits= (TYPE)max_bit;
while (bits <<= 1)
max_bit= bits;
}
TYPE reverse_int(TYPE arg)
{
TYPE bit_setter= 1, bit_tester= max_bit, result= 0;
for (result= 0; bit_tester; bit_tester>>= 1, bit_setter<<= 1)
if (arg & bit_tester)
result|= bit_setter;
return result;
}
Primero solo se necesita ejecutar reverse_int_setup(), que almacena un número entero con el bit más alto activado, luego cualquier llamada a reverse_int(argumento) devoluciones argumento con sus bits invertidos (para ser usado como clave para un árbol binario, tomado de un contador creciente, pero eso es más o menos irrelevante).
¿Existe una forma independiente de la plataforma de tener en tiempo de compilación el valor correcto para max_int después de la llamada a reverse_int_setup();De lo contrario, ¿existe algún algoritmo que consideres? mejor/más delgado que el que tengo para reverse_int()?
Gracias.
Solución
#include<stdio.h>
#include<limits.h>
#define TYPE_BITS sizeof(TYPE)*CHAR_BIT
typedef unsigned long TYPE;
TYPE reverser(TYPE n)
{
TYPE nrev = 0, i, bit1, bit2;
int count;
for(i = 0; i < TYPE_BITS; i += 2)
{
/*In each iteration, we swap one bit on the 'right half'
of the number with another on the left half*/
count = TYPE_BITS - i - 1; /*this is used to find how many positions
to the left (and right) we gotta move
the bits in this iteration*/
bit1 = n & (1<<(i/2)); /*Extract 'right half' bit*/
bit1 <<= count; /*Shift it to where it belongs*/
bit2 = n & 1<<((i/2) + count); /*Find the 'left half' bit*/
bit2 >>= count; /*Place that bit in bit1's original position*/
nrev |= bit1; /*Now add the bits to the reversal result*/
nrev |= bit2;
}
return nrev;
}
int main()
{
TYPE n = 6;
printf("%lu", reverser(n));
return 0;
}
Esta vez he usado la idea de 'número de bits' de TK, pero la hice algo más portátil al no asumir que un byte contiene 8 bits y en su lugar usar la macro CHAR_BIT.El código es más eficiente ahora (con el bucle for interno eliminado).Espero que el código también sea un poco menos críptico esta vez.:)
La necesidad de usar el conteo es que el número de posiciones en las que tenemos que desplazarnos un bit varía en cada iteración: tenemos que mover el bit más a la derecha en 31 posiciones (asumiendo un número de 32 bits), el segundo bit más a la derecha en 29 posiciones y así en.Por lo tanto, el recuento debe disminuir con cada iteración a medida que i aumenta.
Espero que esa información resulte útil para comprender el código...
Otros consejos
El siguiente programa sirve para demostrar un algoritmo más sencillo para invertir bits, que puede ampliarse fácilmente para manejar números de 64 bits.
#include <stdio.h>
#include <stdint.h>
int main(int argc, char**argv)
{
int32_t x;
if ( argc != 2 )
{
printf("Usage: %s hexadecimal\n", argv[0]);
return 1;
}
sscanf(argv[1],"%x", &x);
/* swap every neigbouring bit */
x = (x&0xAAAAAAAA)>>1 | (x&0x55555555)<<1;
/* swap every 2 neighbouring bits */
x = (x&0xCCCCCCCC)>>2 | (x&0x33333333)<<2;
/* swap every 4 neighbouring bits */
x = (x&0xF0F0F0F0)>>4 | (x&0x0F0F0F0F)<<4;
/* swap every 8 neighbouring bits */
x = (x&0xFF00FF00)>>8 | (x&0x00FF00FF)<<8;
/* and so forth, for say, 32 bit int */
x = (x&0xFFFF0000)>>16 | (x&0x0000FFFF)<<16;
printf("0x%x\n",x);
return 0;
}
Este código no debe contener errores y se probó usando 0x12345678 para producir 0x1e6a2c48, que es la respuesta correcta.
typedef unsigned long TYPE;
TYPE reverser(TYPE n)
{
TYPE k = 1, nrev = 0, i, nrevbit1, nrevbit2;
int count;
for(i = 0; !i || (1 << i && (1 << i) != 1); i+=2)
{
/*In each iteration, we swap one bit
on the 'right half' of the number with another
on the left half*/
k = 1<<i; /*this is used to find how many positions
to the left (or right, for the other bit)
we gotta move the bits in this iteration*/
count = 0;
while(k << 1 && k << 1 != 1)
{
k <<= 1;
count++;
}
nrevbit1 = n & (1<<(i/2));
nrevbit1 <<= count;
nrevbit2 = n & 1<<((i/2) + count);
nrevbit2 >>= count;
nrev |= nrevbit1;
nrev |= nrevbit2;
}
return nrev;
}
Esto funciona bien en gcc en Windows, pero no estoy seguro de si es completamente independiente de la plataforma.Algunos lugares de preocupación son:
la condición en el bucle for: se supone que cuando dejaste Shift 1 más allá del bit más a la izquierda, obtienes un 0 con el 1 "cayendo" (lo que esperaría y lo que el viejo Turbo C da iirc), o el 1 da vueltas y obtienes un 1 (lo que parece ser el comportamiento de gcc).
la condición en el bucle while interno:véase más arriba.Pero aquí sucede algo extraño:En este caso, gcc parece dejar que el 1 se caiga y no dé vueltas.
El código puede resultar críptico:Si está interesado y necesita una explicación, no dude en preguntar. La colocaré en algún lugar.
@ΤΖΩΤΖΙΟΥ
En respuesta a los comentarios de ΤΖΩΤΖΙΟΥ, presento una versión modificada de lo anterior que depende de un límite superior para el ancho de bits.
#include <stdio.h>
#include <stdint.h>
typedef int32_t TYPE;
TYPE reverse(TYPE x, int bits)
{
TYPE m=~0;
switch(bits)
{
case 64:
x = (x&0xFFFFFFFF00000000&m)>>16 | (x&0x00000000FFFFFFFF&m)<<16;
case 32:
x = (x&0xFFFF0000FFFF0000&m)>>16 | (x&0x0000FFFF0000FFFF&m)<<16;
case 16:
x = (x&0xFF00FF00FF00FF00&m)>>8 | (x&0x00FF00FF00FF00FF&m)<<8;
case 8:
x = (x&0xF0F0F0F0F0F0F0F0&m)>>4 | (x&0x0F0F0F0F0F0F0F0F&m)<<4;
x = (x&0xCCCCCCCCCCCCCCCC&m)>>2 | (x&0x3333333333333333&m)<<2;
x = (x&0xAAAAAAAAAAAAAAAA&m)>>1 | (x&0x5555555555555555&m)<<1;
}
return x;
}
int main(int argc, char**argv)
{
TYPE x;
TYPE b = (TYPE)-1;
int bits;
if ( argc != 2 )
{
printf("Usage: %s hexadecimal\n", argv[0]);
return 1;
}
for(bits=1;b;b<<=1,bits++);
--bits;
printf("TYPE has %d bits\n", bits);
sscanf(argv[1],"%x", &x);
printf("0x%x\n",reverse(x, bits));
return 0;
}
Notas:
- gcc advertirá sobre las constantes de 64 bits
- los printfs también generarán advertencias
- Si necesita más de 64 bits, el código debe ser lo suficientemente simple como para extenderlo.
Pido disculpas de antemano por los delitos de codificación que cometí anteriormente: ¡misericordia, buen señor!
Hay una buena colección de "Bit Twiddling Hacks", que incluye una variedad de algoritmos de inversión de bits simples y no tan simples codificados en C en http://graphics.stanford.edu/~seander/bithacks.html.
Personalmente me gusta el algoritmo "Obvio" (http://graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious) porque, bueno, es obvio.Algunos de los otros pueden requerir menos instrucciones para ejecutarse.Si realmente necesito optimizar algo, puedo elegir las versiones no tan obvias pero más rápidas.De lo contrario, por motivos de legibilidad, mantenibilidad y portabilidad, elegiría el Obvio.
Aquí hay una variación más útil en general.Su ventaja es su capacidad para funcionar en situaciones en las que se desconoce la longitud de bits del valor que se va a invertir (la palabra clave), pero se garantiza que no excederá un valor que llamaremos maxLength.Un buen ejemplo de este caso es la descompresión del código Huffman.
El siguiente código funciona con palabras de código de 1 a 24 bits de longitud.Ha sido optimizado para una ejecución rápida en un Pentium D.Tenga en cuenta que accede a la tabla de búsqueda hasta 3 veces por uso.Experimenté con muchas variaciones que redujeron ese número a 2 a expensas de una tabla más grande (4096 y 65,536 entradas).Esta versión, con la tabla de 256 bytes, fue la clara ganadora, en parte porque es muy ventajoso que los datos de la tabla estén en las cachés, y quizás también porque el procesador tiene una instrucción de búsqueda/traducción de tablas de 8 bits.
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};
const unsigned short masks[17] =
{0,0,0,0,0,0,0,0,0,0X0100,0X0300,0X0700,0X0F00,0X1F00,0X3F00,0X7F00,0XFF00};
unsigned long codeword; // value to be reversed, occupying the low 1-24 bits
unsigned char maxLength; // bit length of longest possible codeword (<= 24)
unsigned char sc; // shift count in bits and index into masks array
if (maxLength <= 8)
{
codeword = table[codeword << (8 - maxLength)];
}
else
{
sc = maxLength - 8;
if (maxLength <= 16)
{
codeword = (table[codeword & 0X00FF] << sc)
| table[codeword >> sc];
}
else if (maxLength & 1) // if maxLength is 17, 19, 21, or 23
{
codeword = (table[codeword & 0X00FF] << sc)
| table[codeword >> sc] |
(table[(codeword & masks[sc]) >> (sc - 8)] << 8);
}
else // if maxlength is 18, 20, 22, or 24
{
codeword = (table[codeword & 0X00FF] << sc)
| table[codeword >> sc]
| (table[(codeword & masks[sc]) >> (sc >> 1)] << (sc >> 1));
}
}
Qué tal si:
long temp = 0;
int counter = 0;
int number_of_bits = sizeof(value) * 8; // get the number of bits that represent value (assuming that it is aligned to a byte boundary)
while(value > 0) // loop until value is empty
{
temp <<= 1; // shift whatever was in temp left to create room for the next bit
temp |= (value & 0x01); // get the lsb from value and set as lsb in temp
value >>= 1; // shift value right by one to look at next lsb
counter++;
}
value = temp;
if (counter < number_of_bits)
{
value <<= counter-number_of_bits;
}
(Supongo que sabes cuántos bits contiene el valor y está almacenado en número_de_bits)
Obviamente, la temperatura debe ser el tipo de datos más largo imaginable y cuando copia la temperatura nuevamente al valor, todos los bits extraños en la temperatura deberían desaparecer mágicamente (¡creo!).
O, la forma 'c' sería decir:
while(value)
tu elección
Podemos almacenar los resultados de invertir todas las secuencias posibles de 1 byte en una matriz (256 entradas distintas), luego usar una combinación de búsquedas en esta tabla y algo de lógica oring para obtener el reverso del número entero.
Aquí hay una variación y corrección de la solución de TK que podría ser más clara que las soluciones de Sundar.Toma bits individuales de t y los envía a return_val:
typedef unsigned long TYPE;
#define TYPE_BITS sizeof(TYPE)*8
TYPE reverser(TYPE t)
{
unsigned int i;
TYPE return_val = 0
for(i = 0; i < TYPE_BITS; i++)
{/*foreach bit in TYPE*/
/* shift the value of return_val to the left and add the rightmost bit from t */
return_val = (return_val << 1) + (t & 1);
/* shift off the rightmost bit of t */
t = t >> 1;
}
return(return_val);
}
El enfoque genérico que funcionaría para objetos de cualquier tipo y tamaño sería invertir el número de bytes del objeto e invertir el orden de los bits en cada byte.En este caso, el algoritmo a nivel de bits está vinculado a un número concreto de bits (un byte), mientras que la lógica "variable" (con respecto al tamaño) se eleva al nivel de bytes completos.
Aquí está mi generalización de la solución de freespace (en caso de que algún día tengamos máquinas de 128 bits).Da como resultado un código sin saltos cuando se compila con gcc -O3 y, obviamente, es insensible a la definición de foo_t en máquinas sanas.¡Desafortunadamente depende de que el cambio sea una potencia de 2!
#include <limits.h>
#include <stdio.h>
typedef unsigned long foo_t;
foo_t reverse(foo_t x)
{
int shift = sizeof (x) * CHAR_BIT / 2;
foo_t mask = (1 << shift) - 1;
int i;
for (i = 0; shift; i++) {
x = ((x & mask) << shift) | ((x & ~mask) >> shift);
shift >>= 1;
mask ^= (mask << shift);
}
return x;
}
int main() {
printf("reverse = 0x%08lx\n", reverse(0x12345678L));
}
En caso de que la inversión de bits sea crítica en términos de tiempo, y principalmente en conjunto con FFT, lo mejor es almacenar toda la matriz de bits invertidos.En cualquier caso, esta matriz será de menor tamaño que las raíces de la unidad que deben calcularse previamente en el algoritmo FFT Cooley-Tukey.Una forma sencilla de calcular la matriz es:
int BitReverse[Size]; // Size is power of 2
void Init()
{
BitReverse[0] = 0;
for(int i = 0; i < Size/2; i++)
{
BitReverse[2*i] = BitReverse[i]/2;
BitReverse[2*i+1] = (BitReverse[i] + Size)/2;
}
} // end it's all
