Conversion d’un entier en chaîne sans access aux bibliothèques

J’ai récemment lu un exemple de question d’entrevue d’emploi:

Ecrivez une fonction pour convertir un entier en chaîne. Supposons que vous n’ayez pas access aux fonctions de la bibliothèque, par exemple itoa (), etc …

Comment vous y prendriez-vous?

coup rapide: (édité pour gérer les nombres négatifs)

 int n = INT_MIN; char buffer[50]; int i = 0; bool isNeg = n<0; unsigned int n1 = isNeg ? -n : n; while(n1!=0) { buffer[i++] = n1%10+'0'; n1=n1/10; } if(isNeg) buffer[i++] = '-'; buffer[i] = '\0'; for(int t = 0; t < i/2; t++) { buffer[t] ^= buffer[it-1]; buffer[it-1] ^= buffer[t]; buffer[t] ^= buffer[it-1]; } if(n == 0) { buffer[0] = '0'; buffer[1] = '\0'; } printf(buffer); 

L’algorithme est facile à voir en anglais.

Étant donné un entier, par exemple 123

  1. diviser par 10 => 123/10. Rendement, résultat = 12 et rest = 3

  2. append 30h à 3 et pousser sur la stack (append 30h convertira 3 en représentation ASCII)

  3. répéter l’étape 1 jusqu’à ce que le résultat soit <10

  4. ajoute 30h au résultat et stocke sur stack

  5. la stack contient le nombre dans l’ordre de | 1 | 2 | 3 | …

Un coup d’œil sur le Web pour la mise en œuvre d’itoa vous donnera de bons exemples. En voici une, évitant d’inverser la chaîne à la fin. Il repose sur un tampon statique, aussi soyez prudent si vous le réutilisez pour des valeurs différentes.

 char* itoa(int val, int base){ static char buf[32] = {0}; int i = 30; for(; val && i ; --i, val /= base) buf[i] = "0123456789abcdef"[val % base]; return &buf[i+1]; } 

En supposant que ce soit en décimal, alors comme ceci:

  int num = ...; char res[MaxDigitCount]; int len = 0; for(; num > 0; ++len) { res[len] = num%10+'0'; num/=10; } res[len] = 0; //null-terminating //now we need to reverse res for(int i = 0; i < len/2; ++i) { char c = res[i]; res[i] = res[len-i-1]; res[len-i-1] = c; } 

Je garderai à l’esprit que tous les caractères numériques sont dans l’ordre croissant dans le jeu de caractères ASCII et n’ont pas d’autres caractères entre eux.

Je voudrais également utiliser les opérateurs / et % plusieurs resockets.

La façon dont j’obtiendrais la mémoire pour la chaîne dépendrait des informations que vous n’avez pas données.

Une implémentation de la fonction itoa() semble être une tâche facile, mais en réalité, vous devez prendre en charge de nombreux aspects liés à vos besoins. J’imagine que dans l’entretien, vous êtes censé donner des détails sur votre solution à la solution plutôt que de copier une solution disponible sur Google ( http://en.wikipedia.org/wiki/Itoa ).

Voici quelques questions que vous voudrez peut-être vous poser ou poser à l’intervieweur:

  • Où la chaîne doit-elle être localisée (malloced? Transmis par l’utilisateur? Variable statique?)
  • Devrais-je supporter les numéros signés?
  • Devrais-je supporter le virgule flottante?
  • Devrais-je supporter d’autres bases plutôt que 10?
  • Avons-nous besoin d’une vérification des entrées?
  • La chaîne de sortie est-elle limitée dans legth?

Etc.

Voici une approche simple, mais je suppose que si vous le présentez tel quel sans le comprendre et le paraphraser, votre professeur saura que vous venez de copier le contenu du réseau:

 char *pru(unsigned x, char *eob) { do { *--eob = x%10; } while (x/=10); return eob; } char *pri(int x, char *eob) { eob = fmtu(x<0?-x:x, eob); if (x<0) *--eob='-'; return eob; } 

Diverses améliorations sont possibles, notamment si vous souhaitez intmax_t tailles entières supérieures à un mot allant jusqu'à intmax_t . Je vous laisse le soin de comprendre comment ces fonctions sont appelées.

Légèrement plus long que la solution:

 static char* itoa(int n, char s[]) { int i, sign; if ((sign = n) < 0) n = -n; i = 0; do { s[i++] = n % 10 + '0'; } while ((n /= 10) > 0); if (sign < 0) s[i++] = '-'; s[i] = '\0'; reverse(s); return s; } 

Sens inverse:

 int strlen(const char* str) { int i = 0; while (str != '\0') { i++; str++; } return i; } static void reverse(char s[]) { int i, j; char c; for (i = 0, j = strlen(s)-1; i 

Et bien que la décision davolno longtemps voici quelques fonctionnalités utiles pour les débutants. J'espère que vous serez utile.

Le plus vite sera le mieux?

 unsigned int findDigits(long long x) { int i = 1; while ((x /= 10) && ++i); return i; } // return the number of digits in x. unsigned int digits(long long x) { x < 0 ? x = -x : 0; return x < 10 ? 1 : x < 100 ? 2 : x < 1000 ? 3 : x < 10000 ? 4 : x < 100000 ? 5 : x < 1000000 ? 6 : x < 10000000 ? 7 : x < 100000000 ? 8 : x < 1000000000 ? 9 : x < 10000000000 ? 10 : findDigits(x); } char tochar(unsigned short from) { return from == 0 ? '0' : from == 1 ? '1' : from == 1 ? '1' : from == 2 ? '2' : from == 3 ? '3' : from == 4 ? '4' : from == 5 ? '5' : from == 6 ? '6' : from == 7 ? '7' : from == 8 ? '8' : from == 9 ? '9' : '\0'; } char * tostring(long long from) { unsigned char negative = from < 0; unsigned int i = digits(from); char* to = (char*)calloc(1, i + negative); if (negative && (*to = '-') & (from = -from) & i++); *(to + i) = 0; while ((i>0+negative) && (*(to + (--i)) = tochar(((from) % 10))) | (from /= 10)); return to; } 

Si vous voulez déboguer, vous pouvez scinder les conditions (instructions) en
lignes de code à l’intérieur des champs while {} .