Как преобразовать произвольное большое целое число из базы 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, добавьте перенос, сохраните новое значение в массиве, новое значение переноса будет новым значением 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);
}

Answer 2

Я написал статью , в которой описывается простое решение на 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), '')

Answer 3

По-настоящему сложной частью является "произвольно большое" целое число без знака.

Вы пытались использовать GNU MP Bignum библиотека?

Answer 4

Unix dc может выполнять базовые преобразования для произвольных больших целых чисел. Открытый исходный код BSD доступен здесь .

Answer 5

Вот библиотека BigInt:

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

Не знаю, работает ли это, но это первый, который я нашел в Google. Похоже, у него есть функции для анализа и форматирования больших целых чисел, поэтому они могут также поддерживать разные базы.

Редактировать: Ааа, вы используете C, моя ошибка. Но вы можете найти идеи в коде, или у кого-то, использующего .NET, может возникнуть такой же вопрос, поэтому я оставлю это здесь.

Answer 6

Вот вышеупомянутый алгоритм, реализованный в 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'));

Answer 7

Python:

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