convierten eficientemente entre Hex, binario, y decimal en C/C++

Question

tengo 3 representaciones de base para los números enteros positivos:

1. decimal, en la variable de largo sin signo (por ejemplo int largo sin signo NDec = 200).
2. Hex, en variable de cadena (por ejemplo cadena NumHex = "C8")
3. binario, en la cadena variable (por ejemplo cadena NumBin = "11001000")

Quiero ser capaz de convierta 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 del tiempo: el tiempo de ejecución más corto.

Answer 1

Como han señalado otros, comenzarí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. Diré, sin embargo, 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 y demás. Para algunos dominios, es posible superar las funciones de la biblioteca.

Por lo tanto, medir primero, y si el rendimiento de éstos conversión 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 instrucciones if(), y luego recurrir a las funciones genéricas de la biblioteca. 2) Use una tabla de consulta si los 100 números más comunes, y luego recurra a una función de biblioteca. Recuerde que es posible que las tablas grandes no quepan en su caché y que requieran varias indirecciones para bibliotecas compartidas, así que mida estas cosas cuidadosamente para asegurarse de que no está disminuyendo el rendimiento.

Es posible que también desee consultar las funciones boost lexical_cast, aunque en mi experiencia estas últimas se comparan relativamente con las buenas funciones antiguas de C.

Duro, muchos lo han dicho, vale la pena repetirlo una y otra vez: no optimice estas conversiones hasta que tenga evidencia 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 de unidad para su propia versión, ya que presentará errores :-(

Answer 2

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

Para facilitar la lectura y facilitar su implementación, al menos debe implementar Dec2Hex() y Dec2Binary() simplemente llamando al strotul(). Eso los convierte en frases únicas, lo cual es muy eficiente para al menos algunas de las interpretaciones anteriores de la palabra.

Answer 3

se parece mucho a un problema de tarea, pero qué diablos ...

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

Luego, para cada byte en su int largo solo tiene que buscar la cadena correcta y concatenarlos.

Para convertir desde cadenas de longitud a larga, 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 utilizar las mismas tablas de búsqueda para la conversión hacia atrás mediante la búsqueda binaria para encontrar la cadena correcta. Esto tomaría log (256) = 8 comparaciones de sus cadenas. Lamentablemente, no tengo tiempo para analizar si la comparación de cadenas sería mucho más rápida que multiplicar y sumar números enteros.

Answer 4

Sugeriría simplemente usar sprintf y sscanf.

Además, si está interesado en cómo se implementa, puede echar un vistazo al source code para glibc, the GNU C Library.

Answer 5

¿Por qué no usar simplemente una macro para tomar también 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 varias macroes.

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

Answer 6

¿Por qué estas rutinas tienen que ser tan eficientes en el tiempo? Ese tipo de afirmación siempre me hace preguntarme. ¿Estás seguro de que los métodos obvios de conversión como strtol() son demasiado lentos o que puedes hacerlo mejor? 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 distintos de '0' y '1', ¿entonces qué? ¿Abortar? Propagar errores masivos?

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

La transformación entre formatos de texto binarios y hexadecimales se puede realizar de forma rápida y eficiente, con tablas de búsqueda, pero todo lo que involucre el formato de texto decimal será más complicado.

Answer 7

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

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

Así que vamos a asumir que su entrada es cuerdo, entonces el corazón de su conversión es la siguiente:

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) 

Vea lo fácil que es? Y fallará en entradas que no sean cuerdas. La mayor parte de tu trabajo se destinará a hacer que tu entrada funcione, no a la performance.

Ahora, este código aprovecha la potencia de dos cambios. Es fácil de extender a base 4, base 8, base 32, etc. No funcionará en la no potencia de dos bases. Para aquellos, tus matemáticas tienen que cambiar. Usted obtiene

val = (val * base) + digit 

que es conceptualmente igual para este conjunto de operaciones. La multiplicación por la base va a ser equivalente al cambio. Por lo tanto, es probable que use una rutina completamente general. Y desinfecte el código mientras desinfecta las entradas. Y en ese punto, strtoul es probablemente tu mejor apuesta. Aquí hay un enlace al a version de strtoul. Casi todo el trabajo consiste en manejar las condiciones de borde, lo que debería darte una pista sobre dónde debes centrar tus energías: código correcto y resistente. El ahorro en el uso de los cambios de bits va a ser mínimo en comparación con el ahorro de, por ejemplo, no se bloquea en la entrada incorrecta.