Convierta eficientemente entre hexadecimal, binario y decimal en C / C ++

Question

Tengo 3 representaciones base para números enteros positivos:

1. Decimal, en variable larga sin signo (por ejemplo, unsigned long int NumDec = 200 ).
2. Hex, en variable de cadena (por ejemplo, cadena NumHex = " C8 " )
3. Binario, en variable de cadena (por ejemplo, cadena NumBin = " 11001000 " )

Quiero poder convertir entre números en las 3 representaciones de la manera más eficiente. Es decir. para implementar las siguientes 6 funciones:

unsigned long int Binary2Dec(const string & Bin) {}
unsigned long int Hex2Dec(const string & Hex) {}
string Dec2Hex(unsigned long int Dec) {}
string Binary2Hex(const string & Bin) {}
string Dec2Binary(unsigned long int Dec) {}
string Hex2Binary(const string & Hex) {}

¿Cuál es el enfoque más eficiente para cada uno de ellos? Puedo usar C y C ++, pero no aumentar.

Editar: Por " eficiencia " Me refiero a la eficiencia de tiempo: el tiempo de ejecución más corto.

Answer 1

Como han señalado otros, empezaría con sscanf ( ) , printf () y / o strtoul () . Son lo suficientemente rápidos para la mayoría de las aplicaciones y es menos probable que tengan errores. Sin embargo, diré que estas funciones son más genéricas de lo que cabría esperar, ya que tienen que tratar con conjuntos de caracteres que no son ASCII, con números representados en cualquier base, etc. Para algunos dominios es posible superar las funciones de la biblioteca.

Entonces, mida primero, y si el rendimiento de estas conversiones es realmente un problema, entonces:

1) En algunas aplicaciones / dominios, ciertos números aparecen muy a menudo, por ejemplo, cero, 100, 200, 19.95, puede ser tan común que tiene sentido optimizar sus funciones para convertir dichos números con un montón de declaraciones if () , y luego volver a las funciones genéricas de la biblioteca. 2) Utilice una búsqueda de tabla si los 100 números más comunes, y luego recurra a una función de biblioteca. Recuerde que las tablas grandes pueden no caber en su caché y pueden requerir múltiples direcciones para las bibliotecas compartidas, así que mida estas cosas con cuidado para asegurarse de que no esté disminuyendo el rendimiento.

También es posible que desee ver las funciones boost lexical_cast, aunque en mi experiencia estas últimas son relativamente comparadas con las buenas funciones antiguas de C.

Muchos lo han dicho, vale la pena repetirlo una y otra vez: no optimices estas conversiones hasta que tengas pruebas de que son un problema. Si optimiza, mida su nueva implementación para asegurarse de que sea más rápida y asegúrese de tener un montón de pruebas unitarias para su propia versión, porque introducirá errores :-(

Answer 2

Sugeriría usar sprintf y sscanf .

Además, si está interesado en cómo se implementa, puede echar un vistazo al código fuente para glibc, la Biblioteca de GNU C .

Answer 3

¿Por qué estas rutinas tienen que ser tan eficientes en el tiempo? Ese tipo de reclamo siempre me hace preguntarme. ¿Estás seguro de que los métodos de conversión obvios como strtol () son demasiado lentos o que puedes mejorar? Las funciones del sistema suelen ser bastante eficientes. A veces son más lentos para admitir la generalidad y la comprobación de errores, pero debe considerar qué hacer con los errores. Si un argumento bin tiene caracteres que no sean '0' y '1', ¿entonces qué? ¿Abortar? ¿Propagar errores masivos?

¿Por qué estás usando " Diciembre " ¿Representar la representación interna? Dec, Hex, y Bin deben usarse para referirse a las representaciones de cadena. No hay nada decimal sobre un unsigned long . ¿Estás tratando con cadenas que muestran el número en decimal? Si no, estás confundiendo a la gente aquí y vas a confundir a muchos más.

La transformación entre los formatos de texto binario y hexadecimal se puede realizar de manera rápida y eficiente, con tablas de búsqueda, pero todo lo relacionado con el formato de texto decimal será más complicado.

Answer 4

Eso depende de lo que estés optimizando, ¿qué quieres decir con " eficiente " ;? ¿Es importante que las conversiones sean rápidas, usen poca memoria, poco tiempo de programador, menos WTFs de otros programadores que leen el código? , o que?

Para facilitar la lectura y facilitar la implementación, al menos debe implementar tanto Dec2Hex () como Dec2Binary () simplemente llamando a strotul () . Eso los convierte en una sola línea, que es muy eficiente para al menos algunas de las interpretaciones anteriores de la palabra.

Answer 5

Suena muy parecido a un problema de tarea, pero qué diablos ...

La respuesta corta es para convertir desde largo int a sus cadenas use dos tablas de búsqueda. Cada tabla debe tener 256 entradas. Uno asigna un byte a una cadena hex: 0 - > " 00 " ;, 1 - > " 01 " ;, etc. El otro asigna un byte a una cadena de bits: 0 - > " 00000000 " ;, 1 - > " 00000001 " ;.

Luego, para cada byte en tu int largo solo tienes que buscar la cadena correcta y concatenarla.

Para convertir de cadenas a largas, simplemente puede convertir la cadena hexadecimal y la cadena de bits a un número decimal multiplicando el valor numérico de cada carácter por la potencia apropiada de 16 o 2, y sumando los resultados.

EDITAR: También puede usar las mismas tablas de búsqueda para la conversión hacia atrás haciendo una búsqueda binaria para encontrar la cadena correcta. Esto tomaría log (256) = 8 comparaciones de sus cadenas. Desafortunadamente, no tengo tiempo para hacer el análisis de si comparar cadenas sería mucho más rápido que multiplicar y sumar enteros.

Answer 6

Pensemos en la mitad de la tarea por un momento: convertir de una base n de cadena a larga sin firmar, donde n es una potencia de 2 (base 2 para binario y base 16 para hex).

Si su entrada es sana, entonces este trabajo no es más que una comparación, un subract, un turno y un dígito. Si tu opinión no es sana, bueno, ahí es donde se pone feo, ¿no es así? Hacer la conversión súper rápida no es difícil. Hacerlo bien en todas las circunstancias es el desafío.

Supongamos que tu opinión es sana, entonces el corazón de tu conversión es este:

unsigned long PowerOfTwoFromString(char *input, int shift)
{
    unsigned long val = 0;
    char upperLimit = 'a' + (1 << shift)
    while (*input) {
        char c = tolower(*input++);
        unsigned long digit = (c > 'a' && c < upperLimit) ? c - 'a' + 10 : c - '0';
        val = (val << shift) | digit;
    }
    return val;
 }

 #define UlongFromBinaryString(str) PowerOfTwoFromString(str, 1)
 #define UlongFromHexString(str) PowerOfTwoFromString(str, 4)

¿Ves lo fácil que es eso? Y fallará en entradas no sanas. La mayor parte de su trabajo se destinará a hacer que su entrada sea sana, no de rendimiento.

Ahora, este código aprovecha la potencia de dos cambios. Es fácil de extender a la base 4, la base 8, la base 32, etc. No funcionará si no se utiliza la potencia de dos bases. Para eso, tu matemática tiene que cambiar. Obtienes

val = (val * base) + digit

que es conceptualmente lo mismo para este conjunto de operaciones. La multiplicación por la base será equivalente al desplazamiento. Así que es más probable que use una rutina completamente general. Y desinfecte el código mientras desinfecta las entradas. Y en ese momento, strtoul es probablemente tu mejor apuesta. Aquí hay un enlace a una versión de strtoul. Casi todo el trabajo consiste en manejar las condiciones de los bordes, lo que debería darle una idea de dónde deben enfocarse sus energías: código correcto y resistente. Los ahorros por el uso de los cambios de bits serán mínimos en comparación con los ahorros de, por ejemplo, no caerse en una mala entrada.

Answer 7

¿Por qué no solo usar una macro para tomar el formato como entrada? Si estás en C al menos.

#define TO_STRING( string, format, data) \
sprintf( string, "##format##", data)
// Int
TO_STRING(buf,%d,i);
// Hex ( Two char representation )
TO_STRING(buf,%02x,i);
// Binary
TO_STRING(buf,%b,i);

O puede usar sprintf directamente: o puede tener múltiples macros.

#define INT_STRING( buf, data) \
sprintf( buf, "%d", data)
#define HEX_STRING( buf, data) \
sprintf( buf, "%x", data)
#define BIN_TO_STRING( buf, data) \
sprintf( buf, "%b", data)

BIN_TO_STRING( loc_buf, my_bin );