Comment convertir un grand entier arbitraire de la base 10 à la base 16?

Le programme nécessite l’entrée d’un grand nombre entier non signé arbitraire, exprimé sous la forme d’une chaîne en base 10. La sortie est une autre chaîne exprimant le nombre entier en base 16.

Par exemple, l’entrée est “1234567890987654321234567890987654321234567890987654321” et la sortie doit être “CE3B5A137DD015278E09864703E4FF9952FF6B62C1CB1”

Plus l’algorithme est rapide, mieux c’est.

Ce sera très facile si l’entrée est limitée à un entier de 32 bits ou de 64 bits; Par exemple, le code suivant peut effectuer la 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; } 

La partie la plus difficile est le nombre entier non signé “arbitraire grand”. J’ai googlé mais la plupart d’entre eux parlent de la conversion en 32 bits ou 64 bits. Aucune chance n’est trouvée.

Quelqu’un peut-il donner n’importe quel coup ou n’importe quel lien qui peut être lu dessus?

Merci d’avance.

Edit Ceci est une question d’entretien que j’ai rencontrée récemment. Quelqu’un peut-il expliquer brièvement comment résoudre ce problème? Je sais qu’il existe une bibliothèque gmp et je l’ai utilisée auparavant; cependant, en tant que question d’entrevue, elle ne nécessite pas l’utilisation d’une bibliothèque externe.

  1. Allouer un tableau d’entiers, le nombre d’éléments est égal à la longueur de la chaîne d’entrée. Initialise le tableau sur tous les 0.

    Ce tableau d’entiers stockera les valeurs en base 16.

  2. Ajoutez les chiffres décimaux de la chaîne d’entrée à la fin du tableau. Multipliez les valeurs existantes par 10, ajoutez le report, stockez une nouvelle valeur dans un tableau, la nouvelle valeur de report est 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, commencez à la 0e entrée et ignore les 0 premiers.


Voici un code qui fonctionnera. Il ne fait aucun doute que quelques optimisations pourraient être apscopes. Mais cela devrait suffire comme solution rapide et sale:

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

J’ai écrit un article décrivant une solution simple en Python qui peut être utilisée pour convertir une série de nombres à partir de bases de nombres arbitraires. J’ai initialement implémenté la solution en C et je ne voulais pas de dépendance à une bibliothèque externe. Je pense que vous devriez être capable de réécrire le code Python très facile en C ou celui que vous préférez.

Voici le code Python:

 import math import ssortingng 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 ssortingng. hexDigits = '0123456789ABCDEF' ssortingng.join((hexDigits[n] for n in base16), '') 

La partie la plus difficile est le nombre entier non signé “arbitraire grand”.

Avez-vous essayé d’utiliser la bibliothèque GNU MP Bignum ?

Unix dc est capable de faire des conversions de base sur de grands entiers arbitraires. Le code source Open BSD est disponible ici .

Voici une bibliothèque BigInt:

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

Aucune idée si cela fonctionne, mais c’est le premier que j’ai trouvé avec Google. Il semble avoir des fonctions pour parsingr et mettre en forme de grands nombres entiers, de sorte qu’ils peuvent également supporter différentes bases.

Edit: Ahh, vous utilisez C, mon erreur. Mais vous pourrez peut-être trouver des idées dans le code ou une personne utilisant .NET aura peut-être la même question. Je vais donc laisser cela ici.

Python:

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

Voici l’algorithme mentionné ci-dessus implémenté en 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(decimalSsortingng) { let hexArray = new Array(decimalSsortingng.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'));