Konvertierung von Integer in String ohne Zugriff auf Bibliotheken

Question

Kürzlich habe ich eine Beispielfrage für ein Vorstellungsgespräch gelesen:

Schreiben Sie eine Funktion zur Umwandlung einer Ganzzahl in eine Zeichenkette. Angenommen, Sie haben keinen Zugang zu Bibliotheksfunktionen, z.B., itoa(), etc...

Wie würden Sie das anstellen?

Answer 1

Eine Implementierung von itoa() Funktion scheint eine einfache Aufgabe zu sein, aber in Wirklichkeit müssen Sie sich um viele Aspekte kümmern, die genau auf Ihre Bedürfnisse abgestimmt sind. Ich vermute, dass im Vorstellungsgespräch von Ihnen erwartet wird, dass Sie einige Details über Ihren Weg zur Lösung angeben, anstatt eine Lösung zu kopieren, die in Google gefunden werden kann ( http://en.wikipedia.org/wiki/Itoa )

Hier sind einige Fragen, die Sie sich selbst oder Ihrem Gesprächspartner stellen sollten:

• Wo soll die Zeichenfolge gespeichert werden (malloced? vom Benutzer übergeben? statische Variable?)
• Sollte ich vorzeichenbehaftete Zahlen unterstützen?
• Sollte ich Gleitkomma unterstützen?
• Sollte ich lieber andere Basen als 10 unterstützen?
• Brauchen wir eine Eingabekontrolle?
• Ist die Länge der Ausgabezeichenfolge begrenzt?

Und so weiter.

Answer 2

Je schneller, desto besser?

unsigned countDigits(long long x)
{
    int i = 1;
    while ((x /= 10) && ++i);
    return i;
}
unsigned getNumDigits(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 : countDigits(x);
}
#define tochar(x) '0' + x
void tostr(char* dest, long long x)
{
    unsigned i = getNumDigits(x);
    char negative = x < 0;
    if (negative && (*dest = '-') & (x = -x) & i++);
    *(dest + i) = 0;
    while ((i > negative) && (*(dest + (--i)) = tochar(((x) % 10))) | (x /= 10));
}

Wenn Sie debuggen wollen, können Sie die Bedingungen (Anweisungen) aufteilen in
Codezeilen innerhalb der while-Bereiche {} .

Answer 3

Konvertierung von Integer in String ohne Zugriff auf Bibliotheken

Wandeln Sie zuerst die niedrigstwertige Ziffer in ein Zeichen um und fahren Sie dann mit den höherwertigen Ziffern fort.

---

Normalerweise würde ich die resultierende String zu platzieren, aber die Rekursion erlaubt es, diesen Schritt mit einem knappen Code zu überspringen.

使用方法 neg_a en myitoa_helper() vermeidet undefiniertes Verhalten mit INT_MIN .

// Return character one past end of character digits.
static char *myitoa_helper(char *dest, int neg_a) {
  if (neg_a <= -10) {
    dest = myitoa_helper(dest, neg_a / 10);
  }
  *dest = (char) ('0' - neg_a % 10);
  return dest + 1;
}

char *myitoa(char *dest, int a) {
  if (a >= 0) {
    *myitoa_helper(dest, -a) = '\0';
  } else {
    *dest = '-';
    *myitoa_helper(dest + 1, a) = '\0';
  }
  return dest;
}

void myitoa_test(int a) {
  char s[100];
  memset(s, 'x', sizeof s);
  printf("%11d <%s>\n", a, myitoa(s, a));
}

Testcode & Ausgabe

#include "limits.h"
#include "stdio.h"

int main(void) {
  const int a[] = {INT_MIN, INT_MIN + 1, -42, -1, 0, 1, 2, 9, 10, 99, 100,
      INT_MAX - 1, INT_MAX};
  for (unsigned i = 0; i < sizeof a / sizeof a[0]; i++) {
    myitoa_test(a[i]);
  }
  return 0;
}

-2147483648 <-2147483648>
-2147483647 <-2147483647>
        -42 <-42>
         -1 <-1>
          0 <0>
          1 <1>
          2 <2>
          9 <9>
         10 <10>
         99 <99>
        100 <100>
 2147483646 <2147483646>
 2147483647 <2147483647>

Answer 4

Ich bin auf diese Frage gestoßen und habe mich entschlossen, bei dem Code vorbeizuschauen, den ich normalerweise für diese Aufgabe verwende:

char *SignedIntToStr(char *Dest, signed int Number, register unsigned char Base) {
    if (Base < 2 || Base > 36) {
        return (char *)0;
    }
    register unsigned char Digits = 1;
    register unsigned int CurrentPlaceValue = 1;
    for (register unsigned int T = Number/Base; T; T /= Base) {
        CurrentPlaceValue *= Base;
        Digits++;
    }
    if (!Dest) {
        Dest = malloc(Digits+(Number < 0)+1);
    }
    char *const RDest = Dest;
    if (Number < 0) {
        Number = -Number;
        *Dest = '-';
        Dest++;
    }
    for (register unsigned char i = 0; i < Digits; i++) {
        register unsigned char Digit = (Number/CurrentPlaceValue);
        Dest[i] = (Digit < 10? '0' : 87)+Digit;
        Number %= CurrentPlaceValue;
        CurrentPlaceValue /= Base;
    }
    Dest[Digits] = '\0';
    return RDest;
}
#include <stdio.h>
int main(int argc, char *argv[]) {
    char String[32];
    puts(SignedIntToStr(String, -100, 16));
    return 0;
}

Dadurch wird automatisch Speicher zugewiesen, wenn NULL an Dest übergeben wird. Andernfalls wird nach Dest geschrieben.

Answer 5

Hier ist ein einfacher Ansatz, aber ich vermute, wenn Sie das so einreichen, ohne es zu verstehen und zu paraphrasieren, wird Ihr Lehrer wissen, dass Sie nur aus dem Internet abgeschrieben haben:

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;
}

Verschiedene Verbesserungen sind möglich, vor allem, wenn Sie effizient größere Integer-Größen als Wörter unterstützen wollen, bis zu intmax_t . Ich überlasse es Ihnen, herauszufinden, wie diese Funktionen aufgerufen werden sollen.