c - tipos - variable flotante
Inversión de bits de un entero, ignorando el tamaño entero y el endianness (12)
Dado un typedef entero:
typedef unsigned int TYPE;
o
typedef unsigned long TYPE;
Tengo el siguiente código para invertir los bits de un 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 entero con el bit más alto activado, luego cualquier llamada a reverse_int ( arg ) devuelve arg con sus bits invertidos (para ser utilizado como clave de un árbol binario, tomado de un aumentar el contador, pero eso es más o menos irrelevante).
¿Hay una manera independiente de la plataforma para tener en tiempo de compilación el valor correcto para max_int después de la llamada a reverse_int_setup (); De lo contrario, ¿hay algún algoritmo que consideres mejor / más simple que el que tengo para reverse_int ()?
Gracias.
Podemos almacenar los resultados de revertir todas las posibles secuencias de 1 byte en una matriz (256 entradas distintas), luego usar una combinación de búsquedas en esta tabla y alguna lógica de ordenamiento para obtener el reverso de un entero.
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 sabe cuántos valores de bits tiene y se almacena en number_of_bits)
Obviamente, la temperatura debe ser el tipo de datos imaginable más largo y cuando copias la temperatura de nuevo en valor, todos los bits extraños en la temperatura deberían desaparecer mágicamente (¡creo!).
O bien, la forma ''c'' sería decir:
while(value)
tu elección
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 empuja hacia 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);
}
@ ΤΖΩΤΖΙΟΥ
En respuesta a los comentarios de ΤΖΩΤΖΙΟΥ, presento la versión modificada de arriba que depende de un límite superior para el ancho de bit.
#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 generarán advertencias también
- Si necesita más de 64 bits, el código debería ser lo suficientemente simple para extender
Pido disculpas de antemano por los crímenes de codificación que cometí antes: ¡misericordia, señor!
El siguiente programa sirve para demostrar un algoritmo más simple para invertir bits, que se puede extender 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ó utilizando 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 si es completamente independiente de la plataforma. Algunos lugares de preocupación son:
la condición en el ciclo for: asume que cuando saliste del turno 1 más allá del bit más a la izquierda, obtienes un 0 con el 1 ''cayendo'' (lo que esperaría y qué buen viejo Turbo C da iirc), o el 1 círculo alrededor y obtienes 1 (lo que parece ser el comportamiento de gcc).
la condición en el ciclo while interno: ver arriba. Pero aquí sucede algo extraño: en este caso, ¡gcc parece dejar que el 1 se caiga y no circule!
El código puede resultar críptico: si está interesado y necesita una explicación, no dude en preguntar: lo pondré en algún lugar.
#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 utilicé 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 sea también menos críptico esta vez. :)
La necesidad de utilizar count es que el número de posiciones por las que tenemos que cambiar un poco varía en cada iteración: tenemos que mover el bit más a la derecha en 31 posiciones (asumiendo el 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 aumenta.
Espero que esa información sea útil para entender el código ...
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 ejecutar. Si realmente necesito optimizar algo así, puedo elegir las versiones no tan obvias pero más rápidas. De lo contrario, para la legibilidad, el mantenimiento y la portabilidad elegiría el Obvio.
Aquí hay una variación más útil en general. Su ventaja es su capacidad para trabajar en situaciones en las que la longitud de bits del valor que se revertirá (la palabra de código) es desconocida, 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 en 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 el claro ganador, en parte porque es muy ventajoso que los datos de la tabla estén en las memorias caché, y quizás también porque el procesador tiene una tabla de búsqueda de 8 bits / instrucciones de traducción.
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));
}
}
El enfoque genérico que funcionaría para los objetos de cualquier tipo, de cualquier tamaño, sería revertir el número de bytes del objeto y el orden inverso de los bits en cada byte. En este caso, el algoritmo de 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 enteros.
Aquí está mi generalización de la solución de freespace (en caso de que algún día obtengamos máquinas de 128 bits). Resulta en código sin salto cuando se compila con gcc -O3, y es obviamente insensible a la definición de foo_t en máquinas sanas. Desafortunadamente, ¡depende de que el cambio sea un poder 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 el caso de que la reversión de bits sea crítica en el tiempo, y principalmente en conjunción con FFT, lo mejor es almacenar todo el conjunto de bits invertidos. En cualquier caso, este conjunto será más pequeño en tamaño que las raíces de la unidad que tienen que ser precalculadas en el algoritmo de FFT Cooley-Tukey. Una manera fácil 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