¿Cómo convertir un entero grande arbitrario de base 10 a base 16?

8 minutos de lectura

avatar de usuario
yinyueyouge

El programa requiere una entrada de un entero arbitrario grande sin signo que se expresa como una cadena en base 10. La salida es otra cadena que expresa el entero en base 16.

Por ejemplo, la entrada es “1234567890987654321234567890987654321234567890987654321”, y la salida será “CE3B5A137DD015278E09864703E4FF9952FF6B62C1CB1”

Cuanto más rápido sea el algoritmo, mejor.

Será muy fácil si la entrada está limitada a enteros de 32 o 64 bits; por ejemplo, el siguiente código puede hacer la conversión:

#define MAX_BUFFER 16
char hex[] = "0123456789ABCDEF";

char* dec2hex(unsigned input) {
    char buff[MAX_BUFFER];
    int i = 0, j = 0;
    char* output;

    if (input == 0) {
        buff[0] = hex[0];
        i = 1;
    } else {
        while (input) {
            buff[i++] = hex[input % 16];
            input = input / 16;
        }
    }

    output = malloc((i + 1) * sizeof(char));
    if (!output) 
        return NULL;

    while (i > 0) {
        output[j++] = buff[--i];        
    }
    output[j] = '\0';

    return output;
}

La parte realmente desafiante es el entero sin signo “arbitrario grande”. He buscado en Google, pero la mayoría de ellos hablan de la conversión dentro de 32 o 64 bits. No se encuentra suerte.

¿Alguien puede dar algún golpe o algún enlace que se pueda leer?

Gracias por adelantado.

Editar Esta es una pregunta de entrevista que encontré recientemente. ¿Alguien puede explicar brevemente cómo resolver este problema? Sé que hay una biblioteca gmp y la utilicé antes; sin embargo, como pregunta de la entrevista, no requiere el uso de una biblioteca externa.

  • @S.Lott – Ese fue mi pensamiento inmediato también

    – Jeff alto

    13 de mayo de 2009 a las 12:08

  • no.. no es tarea; una pregunta de entrevista. :PAG

    – yinyueyouge

    14 de mayo de 2009 a las 5:05

  1. Asigne una matriz de enteros, el número de elementos es igual a la longitud de la cadena de entrada. Inicialice la matriz a todos los 0.

    Esta matriz de enteros almacenará valores en base 16.

  2. Agregue los dígitos decimales de la cadena de entrada al final de la matriz. Multiplique los valores existentes por 10, agregue el remanente, almacene el nuevo valor en la matriz, el nuevo valor remanente es newvalue div 16.

    carryover = digit;
    for (i = (nElements-1); i >= 0; i--)
    {
        newVal = array[index] * 10) + carryover;
        array[index] = newval % 16;
        carryover = newval / 16;
    }
    
  3. imprime la matriz, comienza en la entrada 0 y omite los 0 iniciales.


Aquí hay un código que funcionará. Sin duda, probablemente haya algunas optimizaciones que podrían hacerse. Pero esto debería ser suficiente como una solución rápida y sucia:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "sys/types.h"

char HexChar [16] = { '0', '1', '2', '3', '4', '5', '6', '7',
                      '8', '9', 'A', 'B', 'C', 'D', 'E', 'F' };

static int * initHexArray (char * pDecStr, int * pnElements);

static void addDecValue (int * pMyArray, int nElements, int value);
static void printHexArray (int * pHexArray, int nElements);

static void
addDecValue (int * pHexArray, int nElements, int value)
{
    int carryover = value;
    int tmp = 0;
    int i;

    /* start at the bottom of the array and work towards the top
     *
     * multiply the existing array value by 10, then add new value.
     * carry over remainder as you work back towards the top of the array
     */
    for (i = (nElements-1); (i >= 0); i--)
    {
        tmp = (pHexArray[i] * 10) + carryover;
        pHexArray[i] = tmp % 16;
        carryover = tmp / 16;
    }
}

static int *
initHexArray (char * pDecStr, int * pnElements)
{
    int * pArray = NULL;
    int lenDecStr = strlen (pDecStr);
    int i;

    /* allocate an array of integer values to store intermediate results
     * only need as many as the input string as going from base 10 to
     * base 16 will never result in a larger number of digits, but for values
     * less than "16" will use the same number
     */

    pArray = (int *) calloc (lenDecStr,  sizeof (int));

    for (i = 0; i < lenDecStr; i++)
    {
        addDecValue (pArray, lenDecStr, pDecStr[i] - '0');
    }

    *pnElements = lenDecStr;

    return (pArray);
}

static void
printHexArray (int * pHexArray, int nElements)
{
    int start = 0;
    int i;

    /* skip all the leading 0s */
    while ((pHexArray[start] == 0) && (start < (nElements-1)))
    {
        start++;
    }

    for (i = start; i < nElements; i++)
    {
        printf ("%c", HexChar[pHexArray[i]]);
    }

    printf ("\n");
}

int
main (int argc, char * argv[])
{
    int i;
    int * pMyArray = NULL;
    int nElements;

    if (argc < 2)
    {
        printf ("Usage: %s decimalString\n", argv[0]);
        return (-1);
    }

    pMyArray = initHexArray (argv[1], &nElements);

    printHexArray (pMyArray, nElements);

    if (pMyArray != NULL)
        free (pMyArray);

    return (0);
}

  • Buena solución. Una “optimización” relativa al uso de la memoria sería usar bytes (char o char sin firmar) para cada dígito en lugar de enteros completos.

    – Jeff alto

    14 mayo 2009 a las 12:35

  • La mayoría de los entrevistadores que me han hecho este tipo de preguntas querían que encontrara una solución destructiva sin asignación adicional (después de que presenté una solución como esta). ¿Es eso posible para esta pregunta?

    – Merlyn Morgan-Graham

    1 de mayo de 2011 a las 23:05


  • Nuestro instinto natural es almacenar números en base 10 porque así es como funciona nuestra mente. Me gusta la forma en que cambiaste eso para almacenar en base 16 en su lugar.

    – Mark Ransom

    18 abr a las 15:48

avatar de usuario
jonny dee

he escrito un artículo que describe una solución simple en Python que se puede usar para transformar una serie de números desde y hacia bases numéricas arbitrarias. Originalmente implementé la solución en C y no quería depender de una biblioteca externa. Creo que debería poder reescribir el código Python muy fácil en C o lo que quiera.

Aquí está el código de Python:

import math
import string

def incNumberByValue(digits, base, value):
   # The initial overflow is the 'value' to add to the number.
   overflow = value
   # Traverse list of digits in reverse order.
   for i in reversed(xrange(len(digits))):
      # If there is no overflow we can stop overflow propagation to next higher digit(s).
      if not overflow:
         return
      sum = digits[i] + overflow
      digits[i] = sum % base
      overflow = sum / base

def multNumberByValue(digits, base, value):
   overflow = 0
   # Traverse list of digits in reverse order.
   for i in reversed(xrange(len(digits))):
      tmp = (digits[i] * value) + overflow
      digits[i] = tmp % base
      overflow = tmp / base

def convertNumber(srcDigits, srcBase, destDigits, destBase):
   for srcDigit in srcDigits:
      multNumberByValue(destDigits, destBase, srcBase)
      incNumberByValue(destDigits, destBase, srcDigit)

def withoutLeadingZeros(digits):
   for i in xrange(len(digits)):
      if digits[i] != 0:
         break
   return digits[i:]

def convertNumberExt(srcDigits, srcBase, destBase):
   # Generate a list of zero's which is long enough to hold the destination number.
   destDigits = [0] * int(math.ceil(len(srcDigits)*math.log(srcBase)/math.log(destBase)))
   # Do conversion.
   convertNumber(srcDigits, srcBase, destDigits, destBase)
   # Return result (without leading zeros).
   return withoutLeadingZeros(destDigits)


# Example: Convert base 10 to base 16
base10 = [int(c) for c in '1234567890987654321234567890987654321234567890987654321']
base16 = convertNumberExt(base10, 10, 16)
# Output list of base 16 digits as HEX string.
hexDigits="0123456789ABCDEF"
string.join((hexDigits[n] for n in base16), '')

  • “Este tema aún no existe”.

    – Natalia Adams

    10 de agosto de 2013 a las 3:50

  • Lo sentimos, el artículo referido se ha movido aquí. ¿Te importaría “revocar” tu voto negativo de nuevo?

    – Jonny Dee

    12 de agosto de 2013 a las 18:04

  • Si edita su publicación para incluir los ejemplos de código relevantes para evitar el linkrot, lo votaré.

    – Natalia Adams

    13 de agosto de 2013 a las 2:17

La parte realmente desafiante es el entero sin signo “arbitrario grande”.

¿Has probado a usar Número grande de GNU MP ¿biblioteca?

  • sí, sé gmp y lo usé antes; ¿Se puede resolver este problema sin usar gmp? O bien, ¿puede decir brevemente cómo está diseñado el gmp ya que la base de código es bastante grande?

    – yinyueyouge

    14 de mayo de 2009 a las 5:13

Unix dc es capaz de hacer conversiones de base en enteros grandes arbitrarios. El código fuente de Open BSD está disponible aquí.

avatar de usuario
Daniel Earwicker

Aquí hay una biblioteca BigInt:

http://www.codeproject.com/KB/cs/BigInt.aspx?msg=3038072#xx3038072xx

No tengo idea si funciona, pero es el primero que encontré con Google. Parece tener funciones para analizar y formatear números enteros grandes, por lo que también pueden admitir diferentes bases.

Editar: Ahh, estás usando C, mi error. Pero es posible que pueda obtener ideas del código, o alguien que use .NET puede tener la misma pregunta, así que dejaré esto aquí.

avatar de usuario
Stan tumbas

Pitón:

>>> from string import upper
>>> input = "1234567890987654321234567890987654321234567890987654321"
>>> output = upper(hex(int(input)))[2:-1]
>>> print output
CE3B5A137DD015278E09864703E4FF9952FF6B62C1CB1

avatar de usuario
Pavlo Chervinski

Aquí está el algoritmo mencionado anteriormente implementado en javascript:

function addDecValue(hexArray, value) {
  let carryover = value;
  for (let i = (hexArray.length - 1); i >= 0; i--) {
    let rawDigit = ((hexArray[i] || 0) * 10) + carryover;
    hexArray[i] = rawDigit % 16;
    carryover = Math.floor(rawDigit / 16);
  }
}

function toHexArray(decimalString) {
  let hexArray = new Array(decimalString.length);
  for (let i = 0; i < decimalString.length; i++) {
    addDecValue(hexArray, Number(decimalString.charAt(i)));
  }
  return hexArray;
}

function toHexString(hexArray) {
  const hexDigits = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'];
  let result="";
  for (let i = 0; i < hexArray.length; i++) {
    if (result === '' && hexArray[i] === 0) continue;
    result += hexDigits[hexArray[i]];
  }
  return result
}

toHexString(toHexArray('1234567890987654321234567890987654321234567890987654321'));

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad