Inversión de bits de un entero, ignorando el tamaño del entero y la endianidad

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, bit_setter<<= 1) if (arg & bit_tester) result|= bit_setter; return result; } 

Uno solo 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 usarlos como una 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 comstackción el valor correcto para max_int después de la llamada a reverse_int_setup (); De lo contrario, ¿hay un algoritmo que considere mejor / más delgado que el que tengo para reverse_int ()?

Gracias.

 #include #include #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 ‘cantidad de bits’ de TK, pero la he hecho un poco más portátil al no suponer que un byte contiene 8 bits y, en su lugar, utilizar la macro CHAR_BIT. El código es más eficiente ahora (con el bucle interno interno eliminado). Espero que el código también sea un poco menos críptico esta vez. 🙂

La necesidad de usar conteo es que el número de posiciones en las que tenemos que cambiar un bit varía en cada iteración: tenemos que mover el bit más a la derecha en 31 posiciones (suponiendo un número de 32 bits), el segundo bit más a la derecha en 29 posiciones y así en. Por lo tanto, la cuenta debe disminuir con cada iteración a medida que i aumenta.

Espero que un poco de información sea útil para entender el código …

El siguiente progtwig sirve para demostrar un algoritmo más ágil para invertir los bits, que se puede extender fácilmente para manejar números de 64 bits.

 #include  #include  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<>= count; nrev |= nrevbit1; nrev |= nrevbit2; } return nrev; } 

Esto funciona bien en gcc en Windows, pero no estoy seguro de que sea completamente independiente de la plataforma. Algunos lugares de preocupación son:

  • la condición en el bucle for: asume que cuando dejas el Cambio 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 gira alrededor y obtienes un 1 (lo que parece ser el comportamiento de gcc).

  • la condición en el bucle 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.

@ ΤΖΩΤΖΙΟΥ

En respuesta a los comentarios de ΤΖΩΤΖΙΟΥ, presento la versión modificada de arriba que depende de un límite superior para el ancho de bits.

 #include  #include  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 avisará sobre las constantes de 64 bits
  • Los printfs generarán advertencias también.
  • Si necesita más de 64 bits, el código debe ser lo suficientemente simple como para extenderlo.

Me disculpo de antemano por los crímenes de encoding que cometí anteriormente.

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 “Obvious” ( 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 el problema, puedo elegir las versiones no tan obvias pero más rápidas. De lo contrario, por legibilidad, facilidad de mantenimiento y portabilidad, elegiría el Obvio.

Aquí hay una variación más útil en general. Su ventaja es su capacidad para trabajar en situaciones donde se desconoce la longitud de bits del valor a invertir, la palabra de código, pero se garantiza que no excederá un valor que llamaremos maxLength. Un buen ejemplo de este caso es la descompresión de código de Huffman.

El siguiente código funciona en palabras de código de 1 a 24 bits de longitud. Se ha 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 para los datos de la tabla en los cachés, y quizás también porque el procesador tiene una instrucción de búsqueda / traducción de tabla 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 usted sabe cuántos bits de valor mantiene y se almacena en número_de_bits)

Obviamente, la temperatura debe ser el tipo de datos más largo que se pueda imaginar y, cuando vuelva a copiar la temperatura en su valor, todos los bits extraños de 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 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 oring para obtener el reverso del entero.

Aquí hay una variación y corrección a la solución de TK que podría ser más clara que las soluciones por sundar. Toma bits individuales de t y los empuja en 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 método de enfoque genérico que funcionaría para objetos de cualquier tipo de cualquier tamaño sería invertir los bytes del objeto y revertir el orden 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 completos.

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). Da como resultado un código sin saltos cuando se comstack con gcc-O3, y obviamente es insensible a la definición de foo_t en máquinas sanas. Desafortunadamente, ¡depende de que el turno sea una potencia de 2!

 #include  #include  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 el tiempo, y principalmente en combinación con FFT, lo mejor es almacenar toda la matriz de inversión de bits. En cualquier caso, esta matriz será más pequeña en tamaño que las raíces de la unidad que se deben calcular previamente en el algoritmo FFT Cooley-Tukey. Una forma 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