atoi-Implementierung in C

Lesezeit: 9 Minuten

Benutzer-Avatar
Adam

Folgendes kann ich nicht nachvollziehen atoi Implementierungscode, insbesondere diese Zeile:

k = (k << 3) + (k << 1) + (*p) - '0';

Hier ist der Code:

int my_atoi(char *p) {
    int k = 0;
    while (*p) {
        k = (k << 3) + (k << 1) + (*p) - '0';
        p++;
     }
     return k;
}

Kann es mir jemand erklären?

Eine andere Frage: was sollte der Algorithmus sein atof Implementierung ?

Benutzer-Avatar
Karl Horvath

<< ist Bitverschiebung, (k<<3)+(k<<1) ist k*10geschrieben von jemandem, der dachte, er sei klüger als ein Compiler (naja, er hat sich geirrt …)

(*p) - '0' subtrahiert den Wert des Zeichens 0 von dem Zeichen, auf das gezeigt wird pwodurch das Zeichen effektiv in eine Zahl umgewandelt wird.

Ich hoffe, Sie können den Rest herausfinden … Denken Sie nur daran, wie das Dezimalsystem funktioniert.

Hier ist eine Spezifikation für die Standardfunktion atoi. Entschuldigung, dass ich den Standard nicht zitiere, aber das wird genauso gut funktionieren (von: http://www.cplusplus.com/reference/clibrary/cstdlib/atoi/ )

Die Funktion verwirft zunächst so viele Leerzeichen (wie in
isspace) nach Bedarf, bis das erste Nicht-Leerzeichen gefunden wird. Nimmt dann ausgehend von diesem Zeichen ein optionales einleitendes Plus- oder Minuszeichen, gefolgt von so vielen Ziffern zur Basis 10 wie möglich, und interpretiert sie als numerischen Wert.

Die Zeichenfolge kann nach denen, die die ganze Zahl bilden, weitere Zeichen enthalten, die ignoriert werden und keinen Einfluss auf das Verhalten dieser Funktion haben.

Wenn die erste Folge von Nicht-Leerzeichen in str keine gültige ganze Zahl ist, oder wenn keine solche Folge existiert, weil entweder
str leer ist oder nur Leerzeichen enthält, wird keine Konvertierung durchgeführt und Null zurückgegeben.

  • “er hat sich geirrt” – Ähm, vielleicht, vielleicht auch nicht. Es hängt vom Compiler ab und davon, wann diese Implementierung geschrieben wurde. Vielleicht wurde dies vor einiger Zeit geschrieben, als die Optimierung von Compilern nicht annähernd so gut war. Es gibt keinen Grund, zurückzugehen und es jetzt zu ändern. Autoren von Standardbibliotheksimplementierungen müssen sich mit vielen (viele) mehr Anwendungsfälle als wir normalerweise tun.

    – Ed S.

    9. Oktober 2012 um 0:02 Uhr


  • @EdS.: kann sein mit etwas #ifdefs .. Ich bezweifle, dass Sie dies in einem gängigen Standardbibliothekscode finden werden.

    – Karoly Horvath

    9. Oktober 2012 um 0:03 Uhr

  • @aroth: “Die Verbesserung der Leistung durch Verschleierung von Code ist nie eine gute Idee” – Sie machen ein Stück Code fast immer unverständlicher, wenn Sie es optimieren, und von Zeit zu Zeit wird es tatsächlich ziemlich knifflig (in diesem Fall ist jedoch ein Kommentar angebracht). Manchmal erfordern Dinge wirklich Optimierungen auf sehr niedriger Ebene, und es sei denn, Sie haben diese seltene Art von Benutzern, die sich mehr um die Codequalität als um die Leistung kümmern, ist es einfach albern zu sagen, dass dies “nie eine gute Idee” ist. Ich finde Duffs Gerät möchte sich unterhalten.

    – Ed S.

    9. Oktober 2012 um 0:10 Uhr


  • Ich stimme Ihnen beiden nicht zu. Moores Gesetz endete vor mehr als 5 Jahren; CPUs werden nicht mehr schneller, sie bekommen nur mehr Kerne, was dem Endbenutzer im Allgemeinen nicht spürbar hilft. Es wäre jedoch ein pathologisch schlechter Compiler erforderlich, um nicht die beste Methode zur Durchführung der Multiplikation mit einer Konstanten zu wählen. Das Schreiben der Multiplikation mit 10 als Bitverschiebungen ist keine Optimierung; Es ist ein Ausdruck des Codes in Assemblersprache, den der Compiler auf einer bestimmten Maschine generieren soll, was nicht von C ausgedrückt werden sollte.

    – R.. GitHub HÖR AUF, EIS ZU HELFEN

    9. Oktober 2012 um 4:21 Uhr

  • @R.. – Hurra für Meinungsverschiedenheiten! Obwohl Moores Gesetz ist immer noch stark. Da haben Sie recht die meisten neue Transistoren zielen auf das Hinzufügen von Kernen ab, einige jedoch auf architektonische Verbesserungen, die den IPC erhöhen, und Prozessverbesserungen ermöglichen höhere Taktraten. Die Single-Thread-Leistung verbessert sich also mit jeder Iteration (um etwa 10-20 %). Nicht um das volle 2x, aber immer noch genug, um wahrnehmbar zu sein und Gewinne in den Schatten zu stellen, die durch Verschleierung von Code hier und da erzielt werden könnten.

    – aroth

    10. Oktober 2012 um 0:03 Uhr


Benutzer-Avatar
R.. GitHub HÖREN SIE AUF, ICE ZU HELFEN

k = (k << 3) + (k << 1);

meint

k = k * 2³ + k * 2¹ = k * 8 + k * 2 = k * 10

Hilft das?

Das *p - '0' term addiert den Wert der nächsten Ziffer; Dies funktioniert, weil C erfordert, dass die Ziffern aufeinanderfolgende Werte haben, so dass '1' == '0' + 1, '2' == '0' + 2etc.

Zu deiner zweiten Frage (atof), das sollte eine eigene Frage sein, und es ist das Thema einer Abschlussarbeit, nicht etwas einfach zu beantwortendes …

  • @Adam Der Algorithmus lautet einfach “Multiplizieren Sie für jede neue Ziffer den Wert der vorhergehenden Ziffern mit 10 und addieren Sie die neue Ziffer”. Beachten Sie jedoch die von Karoly Horvath in seiner Antwort erwähnten Probleme, wenn die Eingabe alles andere als Dezimalziffern enthält, erhalten Sie Müll – insbesondere werden keine negativen Zahlen verarbeitet. Und wenn die Eingabe zu lang ist, kommt es zu Überlauf und undefiniertem Verhalten.

    – Daniel Fischer

    9. Oktober 2012 um 0:19 Uhr

  • Jetzt ist es viel besser … können Sie mir den Code dafür ohne Bitwise zeigen? ein anderes Problem, was sollte atof Algorithmus sein?

    – Adam

    9. Oktober 2012 um 0:22 Uhr


  • @DanielFischer tbf, atoi behandelt auch keinen Überlauf

    – Braden Best

    17. August um 18:28 Uhr

#include <stdio.h>
#include <errno.h>
#include <limits.h>

double atof(const char *string);

int debug=1;

int main(int argc, char **argv)
{
    char *str1="3.14159",*str2="3",*str3="0.707106",*str4="-5.2";
    double f1,f2,f3,f4;
    if (debug) printf("convert %s, %s, %s, %s\n",str1,str2,str3,str4);
    f1=atof(str1);
    f2=atof(str2);
    f3=atof(str3);
    f4=atof(str4);

    if (debug) printf("converted values=%f, %f, %f, %f\n",f1,f2,f3,f4);
    if (argc > 1)
    {
        printf("string %s is floating point %f\n",argv[1],atof(argv[1]));
    }
}

double atof(const char *string)
{
    double result=0.0;
    double multiplier=1;
    double divisor=1.0;
    int integer_portion=0;

    if (!string) return result;
    integer_portion=atoi(string);

    result = (double)integer_portion;
    if (debug) printf("so far %s looks like %f\n",string,result);

    /* capture whether string is negative, don't use "result" as it could be 0 */
    if (*string == '-')
    {
        result *= -1; /* won't care if it was 0 in integer portion */
        multiplier = -1;
    }

    while (*string && (*string != '.'))
    {
        string++;
    }
    if (debug) printf("fractional part=%s\n",string);

    // if we haven't hit end of string, go past the decimal point
    if (*string)
    {
        string++;
        if (debug) printf("first char after decimal=%c\n",*string);
    }

    while (*string)
    {
        if (*string < '0' || *string > '9') return result;
        divisor *= 10.0;
        result += (double)(*string - '0')/divisor;
        if (debug) printf("result so far=%f\n",result);
        string++;
    }
    return result*multiplier;
}

  • Dies funktioniert nicht für "1 .1" unter anderen Problemen.

    – chqrlie

    30. April 2019 um 6:54 Uhr

Benutzer-Avatar
John Ko

Interessanterweise zeigt die Manpage für atoi nicht die Einstellung von errno an, wenn Sie also eine Zahl > (2^31)-1 sprechen, haben Sie Pech und ähnlich für Zahlen kleiner als -2^31 (vorausgesetzt 32 -bit int). Sie erhalten eine Antwort, aber es wird nicht das sein, was Sie wollen. Hier ist eine, die einen Bereich von -((2^31)-1) bis (2^31)-1 annehmen und im Fehlerfall INT_MIN (-(2^31)) zurückgeben könnte. errno könnte dann überprüft werden, um zu sehen, ob es übergelaufen ist.

#include <stdio.h>
#include <errno.h>  /* for errno */
#include <limits.h> /* for INT_MIN */
#include <string.h> /* for strerror */

extern int errno;

int debug=0;
int atoi(const char *c)
{
    int previous_result=0, result=0;
    int multiplier=1;

    if (debug) printf("converting %s to integer\n",c?c:"");
    if (c && *c == '-')
    {
        multiplier = -1;
        c++;
    }
    else
    {
        multiplier = 1;
    }
    if (debug) printf("multiplier = %d\n",multiplier);
    while (*c)
    {
        if (*c < '0' || *c > '9')
        {
            return result * multiplier;
        }
        result *= 10;
        if (result < previous_result)
        {
            if (debug) printf("number overflowed - return INT_MIN, errno=%d\n",errno);
            errno = EOVERFLOW;
            return(INT_MIN);
        }
        else
        {
            previous_result *= 10;
        }
        if (debug) printf("%c\n",*c);
        result += *c - '0';

        if (result < previous_result)
        {
            if (debug) printf("number overflowed - return MIN_INT\n");
            errno = EOVERFLOW;
            return(INT_MIN);
        }
        else
        {
            previous_result += *c - '0';
        }
        c++;
    }
    return(result * multiplier);
}

int main(int argc,char **argv)
{
    int result;
    printf("INT_MIN=%d will be output when number too high or too low, and errno set\n",INT_MIN);
    printf("string=%s, int=%d\n","563",atoi("563"));
    printf("string=%s, int=%d\n","-563",atoi("-563"));
    printf("string=%s, int=%d\n","-5a3",atoi("-5a3"));
    if (argc > 1)
    {
        result=atoi(argv[1]);
        printf("atoi(%s)=%d %s",argv[1],result,(result==INT_MIN)?", errno=":"",errno,strerror(errno));
        if (errno) printf("%d - %s\n",errno,strerror(errno));
        else printf("\n");
    }
    return(errno);
}

Benutzer-Avatar
Majid Daryadel

Hier ist meine Implementierung (erfolgreich getestet mit Fällen, die Buchstaben, +, – und Nullen enthalten und mit ihnen beginnen). Ich habe versucht, ein Reverse-Engineering durchzuführen atoi Funktion ein Visuelles Studio. Wenn die Eingabezeichenfolge nur numerische Zeichen enthalten würde, könnte sie in einer Schleife implementiert werden. aber es wird kompliziert, weil Sie sich darum kümmern sollten ,+ und Briefe.

int atoi(char *s)
{    
    int c=1, a=0, sign, start, end, base=1;
//Determine if the number is negative or positive 
    if (s[0] == '-')
        sign = -1;
    else if (s[0] <= '9' && s[0] >= '0')
        sign = 1;
    else if (s[0] == '+')
        sign = 2;
//No further processing if it starts with a letter 
    else 
        return 0;
//Scanning the string to find the position of the last consecutive number
    while (s[c] != '\n' && s[c] <= '9' && s[c] >= '0')
        c++;
//Index of the last consecutive number from beginning
    start = c - 1;
//Based on sign, index of the 1st number is set
    if (sign==-1)       
        end = 1;
    else if (sign==1)
        end = 0;
//When it starts with +, it is actually positive but with a different index 
//for the 1st number
    else
    { 
        end = 1;
        sign = 1;
    }
//This the main loop of algorithm which generates the absolute value of the 
//number from consecutive numerical characters.  
    for (int i = start; i >=end ; i--)
    {
        a += (s[i]-'0') * base;
        base *= 10;
    }
//The correct sign of generated absolute value is applied
    return sign*a;
}

Benutzer-Avatar
Segelfisch009

über atoi() Hinweiscode von hier:

und basierend auf atoi() meine Implementierung von atof():

[have same limitation of original code, doesn’t check length, etc]

double atof(const char* s)
{
  double value_h = 0;
  double value_l = 0;
  double sign = 1;

  if (*s == '+' || *s == '-')
  {
    if (*s == '-') sign = -1;
    ++s;
  }

  while (*s >= 0x30 && *s <= 0x39)
  {
    value_h *= 10;
    value_h += (double)(*s - 0x30);
    ++s;
  }

  // 0x2E == '.'
  if (*s == 0x2E)
  {
    double divider = 1;
    ++s;
    while (*s >= 0x30 && *s <= 0x39)
    {
      divider *= 10;
      value_l *= 10;
      value_l += (double)(*s - 0x30);
      ++s;
    }
    return (value_h + value_l/divider) * sign;
  }
  else
  {
    return value_h * sign;
  }
}

1365590cookie-checkatoi-Implementierung in C

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy