如何将任意大的十进制整数转换为十六进制？

Question

如何将任意大的十进制整数转换为十六进制？

cradix

3

该程序需要输入一个任意大的无符号整数，该整数用十进制表示为一个字符串。输出是另一个字符串，以十六进制表示该整数。

例如，输入为“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库，我以前用过它，但作为一个面试问题，它要求不使用外部库。

- yinyueyouge

@S.Lott - 这也是我的第一反应 - Tall Jeff

1

不是作业，是面试题。 :P - yinyueyouge

8个回答

4

我已经写了一篇文章，描述了一个简单的Python解决方案，可以用于将一系列数字从任意进制转换为另一种进制。我最初是用C实现的这个解决方案，而且我不想依赖外部库。我认为你应该能够将非常简单的Python代码重写为C或者其他语言。

以下是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), '')

- Jonny Dee

此主题尚不存在。 - Natalie Adams

抱歉，所引用的文章已经移动到这里。您是否愿意撤销您的“反对”投票？ - Jonny Dee

如果您编辑帖子并包含相关的代码示例以防止链接失效，我会给您点赞。 - Natalie Adams

2

“真正具有挑战性的部分是那个‘任意大’的无符号整数。” 你是否尝试使用 GNU MP Bignum 库？

- dirkgently

是的，我知道GMP并且以前使用过它；这个问题能否在不使用GMP的情况下解决？或者，您能简要介绍一下GMP的设计吗？因为代码库非常大。 - yinyueyouge

1

你可以尝试这个任意长度的输入C99 base_convert（介于2和62之间）函数：

#include <stdlib.h>
#include <string.h>

static char *base_convert(const char * str, const int base_in, const int base_out) {
    static const char *alphabet = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
    size_t a, b, c = 1, d;
    char *s = malloc(c + 1);
    strcpy_s(s, c + 1, "0");
    for (; *str; ++str) {
        for (a = (char*)memchr(alphabet, *str, base_in) - alphabet, b = c; b;) {
            d = ((char *)memchr(alphabet, s[--b], base_out) - alphabet) * base_in + a;
            s[b] = alphabet[d % base_out];
            a = d / base_out;
        }
        for (; a; s = realloc(s, ++c + 1), memmove(s + 1, s, c), *s = alphabet[a % base_out], a /= base_out);
    }
    return s;
}

在线试用 - 示例用法：

#include <stdio.h>

int main() {
    char * res = base_convert("12345678909876543212345678909876"
                              "54321234567890987654321", 10, 16);
    puts(res);
    free(res);

    // print CE3B5A137DD015278E09864703E4FF9952FF6B62C1CB1
}

示例输出：

'11100100100011101011001001110110001101001001100010100001111011110011000010'
 from base 2 to base 58 is 'BaseConvert62'.

'NdN2mbALtnCHH' from base 60 to base 59 is 'StackOverflow'.

使用您的示例进行了测试，以及Fibonacci(1500000)。

谢谢。

- Michel

1

这是一个BigInt库：

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

不知道它是否有效，但这是我在谷歌上找到的第一个。它似乎具有解析和格式化大整数的功能，因此它们可能也支持不同的基数。

编辑：啊，你正在使用C语言，我的错误。但您可能可以从代码中获取一些想法，或者使用.NET的人可能会有同样的问题，所以我会把它留在这里。

- Daniel Earwicker

1

Unix的dc能够在任意大的整数上进行基本转换。Open BSD源代码可以在这里找到。

- mouviciel

0

Python：

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

- Stan Graves

1

该OP表示这是一个面试问题。当面对“愚蠢”的面试问题时，我（几乎）总是回答一个“愚蠢”的答案。这往往会引发下一部分的对话。该OP选择了C语言...但从未提到答案中需要使用它。大多数“算法”性质的面试问题往往是实现无关的。问题在输入上使用“任意大”的措辞，这暗示着（对我来说）解决方案将基于文本/字符操作...因此我选择了一个具有合理文本操作内置函数的语言。 - Stan Graves

在我看来，问题的本质和给定的标签暗示着一个可接受的解决方案不应该使用任意大小的数字类型，无论是内置的还是库函数。提问者也明确了这一限制。如果你的建议是反抗“愚蠢”的面试问题，那么这只是一个评论而不是答案。如果你的建议是从一个有效的、简单的、真实的解决方案开始，然后逐步推进到更加严格的解决方案（例如，你需要这个实用程序在只有C运行时而没有库的微控制器上工作），那么这只是三个步骤中的第一步。 - Merlyn Morgan-Graham

@MerlynMorgan-Graham 同时，这个问题并没有要求使用任何特定的编程语言。 - ArtOfWarfare

@ArtOfWarfare：标签上写着C。语句“然而，作为一道面试题，它要求不使用外部库”意味着他们所寻找的抽象级别，当谈论C时，实际上是指处理器字节或字的指针算术。为了进一步证明我能够猜测面试官的想法（/半开玩笑），他们会特别问这样的问题，以确保您“理解”指针。 - Merlyn Morgan-Graham

@MerlynMorgan-Graham - 我同意你对OP需求的看法，但没有必要对这个答案进行负评。像我这样的许多人在搜索转换进制算法时会找到这个答案。我对语言的细节不是很感兴趣，而是想看看如何在不确定数字长度的情况下执行此操作的想法。使用Python的搜索者可能会发现这很有用-遗憾的是，我的项目不是Python，而是Obj-C。 - ArtOfWarfare

@ArtOfWarfare：我以前更加咄咄逼人。现在我完全同意你的观点，并且实际上已经去取消了我在你最后一条评论下的踩 :) 不幸的是，直到Stan编辑它之前，它仍然被锁定。 - Merlyn Morgan-Graham

0

这是上述算法在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'));

- Pavlo Chervinskyi

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user106747 · Accepted Answer

分配一个整数数组，元素数量等于输入字符串的长度。将数组初始化为所有0。

这个整数数组将以16进制存储值。

将输入字符串的十进制数字添加到数组末尾。将现有值乘以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 <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);
}