如何将任意大整数从基数10转换为基数16？
该程序需要输入任意大的无符号整数，该整数在基数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库，我之前使用过它; 但作为面试问题，它不需要使用外部库。
-
分配一个整数数组，元素数等于输入字符串的长度。 将数组初始化为全0。
该整数数组将在基数16中存储值。
-
将输入字符串中的十进制数字添加到数组的末尾。 Mulitply现有值加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; } -
打印数组，从第0个条目开始并跳过前导0。
这里有一些可行的代码。 毫无疑问，可能会有一些优化。 但这应该是一个快速而肮脏的解决方案：
#include #include #include #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); }
我写了一篇文章 ，用Python描述了一个简单的解决方案，可用于从一系列数字转换为任意数字基数。 我最初在C中实现了解决方案，我不希望依赖外部库。 我认为你应该能够用C或任何你喜欢的方式重写非常简单的Python代码。
这是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), '')
真正具有挑战性的部分是“任意大”无符号整数。
您是否尝试过使用GNU MP Bignum库？
Unix dc能够对任意大整数进行基本转换。 这里提供Open BSD源代码。
这是一个BigInt库：
http://www.codeproject.com/KB/cs/BigInt.aspx?msg=3038072#xx3038072xx
不知道它是否有效，但它是我在谷歌找到的第一个。 它似乎具有解析和格式化大整数的函数，因此它们也可以支持不同的基数。
编辑：啊，你正在使用C，我的错误。 但是你可以从代码中获取想法，或者使用.NET的人可能会有同样的问题，所以我会把它留在这里。
python：
>>> from string import upper >>> input = "1234567890987654321234567890987654321234567890987654321" >>> output = upper(hex(int(input)))[2:-1] >>> print output CE3B5A137DD015278E09864703E4FF9952FF6B62C1CB1
以下是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'));