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

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.

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

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), '')

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

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

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

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í.

Pitón:

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

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