如何将任意大整数从基数10转换为基数16？

Question

该程序需要输入任意大的无符号整数,该整数在基数10中表示为一个字符串.输出是表示基数16中的整数的另一个字符串.

例如,输入为"1234567890987654321234567890987654321234567890987654321",输出为"CE3B5A137DD015278E09864703E4FF9952FF6B62C1CB1"

算法越快越好.

如果输入限制在32位或64位整数范围内,那将非常容易; 例如,以下代码可以进行转换:

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

真正具有挑战性的部分是"任意大"无符号整数.我用谷歌搜索,但大多数人都在谈论32位或64位的转换.没有找到运气.

任何人都可以给任何点击或任何可以阅读的链接？

提前致谢.

编辑这是我最近遇到的一个面试问题.谁能简单解释一下如何解决这个问题？我知道有一个gmp库,我之前使用过它; 但作为面试问题,它不需要使用外部库.

Answer 1

1. 分配整数数组,元素数等于输入字符串的长度.将数组初始化为全0.

   该整数数组将在基数16中存储值.

2. 将输入字符串中的十进制数字添加到数组的末尾.多个现有值加10个结转,在数组中存储新值,新的结转值为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. 打印数组,从第0个条目开始并跳过前导0.

这里有一些可行的代码.毫无疑问,可能会有一些优化.但这应该是一个快速而肮脏的解决方案:

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