How to convert an arbitrary large integer from base 10 to base 16?

Question

The program requires an input of an arbitrary large unsigned integer which is expressed as one string in base 10. The outputs is another string that expresses the integer in base 16.

For example, the input is "1234567890987654321234567890987654321234567890987654321", and the output shall be "CE3B5A137DD015278E09864703E4FF9952FF6B62C1CB1"

The faster the algorithm the better.

It will be very easy if the input is limited within 32-bit or 64-bit integer; for example, the following code can do the conversion:

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

The real challenging part is the "arbitrary large" unsigned integer. I have googled but most of them are talking about the conversion within 32-bit or 64-bit. No luck is found.

Can anyone give any hit or any link that can be read on?

Thanks in advance.

Edit This is an interview question I encountered recently. Can anyone briefly explain how to solve this problem? I know there is a gmp library and I utilized it before; however as an interview question it requires not using external library.

Answer 1

Here's a BigInt library:

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

No idea if it works, but it's the first one I found with Google. It appears to have functions to parse and format big integers, so they may support different bases too.

Edit: Ahh, you're using C, my mistake. But you may be able to pick up ideas from the code, or someone using .NET may have the same question, so I'll leave this here.

Answer 2

The real challenging part is the "arbitrary large" unsigned integer.

Have you tried using GNU MP Bignum library?

Answer 3

Unix dc is able to do base conversions on arbitrary large integers. Open BSD source code is available here.

Answer 4

man sprintf or snprintf (for the security "stack overflow" types).

Hint, check out the "x" or "X" as your print format.

Answer 5

1) Allocate an array of integers, number of elements is equal to the length of the input string. Initialize the array to all 0s.

This array of integers will store values in base 16.

2) Add the decimal digits from the input string to the end of the array. Mulitply existing values by 10 add carryover, store new value in array, new carryover value is 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) print array, start at 0th entry and skip leading 0s.

---

Here's some code that will works. No doubt there are probably a few optimizations that could be made. But this should suffice as a quick and dirty solution:

#include "stdio.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);
}

Answer 6

Python:

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