Anzahl der Ziffern eines int-Wertes ermitteln



  • Hey,

    kennt jemand ne Möglichkeit die Anzahl der Ziffern eines int-Wertes zu
    ermitteln?


  • Mod

    Mathematiker würden dir jetzt den Logarithmus vorschlagen, aber am schnellsten und einfachsten geht es wohl so:

    unsigned num_digits(unsigned value)
    {
     if (value < 10) return 1;
     if (value < 100) return 2;
     if (value < 1000) return 3;
     if (value < 10000) return 4;
     if (value < 100000) return 5;
     // usw.
    }
    

    Für signed int darfst du dir selber ausdenken, wie du das handhabst.



  • Danke für die schnelle Antwort,
    hmm jetzt ärgere ich mich darüber das ich selber hätte drauf kommen müssen/können.

    Ich hatte die logarithmus methode flüchtig i-wo beim googln überlesen, dann aber gedacht das ich wohl falsch gesucht habe ^^, naja das Forum verführt dazu nicht zu lange selber zu überlegen und schnell mal nachzufragen ;).



  • int ziffern(int val)
    {
      int retval = 1;
      while ((val /= 10))
        ++retval;
      return retval;
    }
    

    @SeppJ
    Was soll das denn? 😃



  • @ cooky451

    Der Code funktioniert doch, weil Integer dividiert werden und der Rest verworfen wird richtig? Somit gibt er 0 an (False), wenn eine Zahl kleiner 10 dividiert wird, korrekt?



  • Ja


  • Mod

    cooky451 schrieb:

    @SeppJ
    Was soll das denn? 😃

    Wieso nicht? Es ist schnell zu schreiben, es ist absolut offensichtlich was der Code tut und vor ein paar Jahren gab es diese Frage schon einmal mit Betonung auf Performance und diese Methode hat sich dort als schnellst erwiesen.

    Schnell, kurz, übersichtlich. Was will man mehr? Man muss ja nicht immer alle Aufgaben maximal abstrahieren.



  • Das dürfte aber vor allem für kleine Zahlen am schnellsten sein, oder?

    Ich werfe mal die Idee der binären Suche in all ihrer Unübersichtlichkeit in die Runde:

    unsigned stellen(unsigned x) {
      if(x < 10000) {
        if(x < 100) {
          if(x < 10) {
            return 1;
          }
          return 2;
        }
        if(x < 1000) {
          return 3;
        }
        return 4;
      }
    
      if(x < 100000000) {
        if(x < 1000000) {
          if(x < 100000) {
            return 5;
          }
          return 6;
        }
        if(x < 10000000) {
          return 7;
        }
        return 8;
      }
    
      if(x  < 1000000000) {
        return 9;
      }
    
      return 10;
    }
    

    ...worin nie mehr als vier Vergleiche benötigt werden. Sofern Geschwindigkeit aber nicht wirklich über allem anderen (insbesondere Wartbarkeit!) steht, kann ich diese Vorgehensweise nicht ernsthaft empfehlen. Wo Performance über allem steht, spielt es eine Rolle, wie schnell die Maschine branchen kann.



  • [Klugscheiss]
    Das ist aber nicht portabel, denn wer weiß schon wie groß ein int (danach wurde ja gefragt) auf dem jeweiligem System ist.
    [\Klugscheiss]

    Deswegen ist die Schleife von cooky451 wohl in den meisten Fällen das Beste.



  • Nirvana134 schrieb:

    Hey,

    kennt jemand ne Möglichkeit die Anzahl der Ziffern eines int-Wertes zu
    ermitteln?

    Try this:

    #include <stdio.h>
    
    unsigned num_length (int n)
    {
        char s[256];
        return sprintf (s, "%d", n);
    }
    
    int main (void)
    {
        printf ("%d\n", num_length (1234));
        printf ("%d\n", num_length (-1234));
    }
    


  • Das düfte wohl so ziemlich die schlechteste Methode sein 😃

    DirkB schrieb:

    Das ist aber nicht portabel, denn wer weiß schon wie groß ein int (danach wurde ja gefragt) auf dem jeweiligem System ist.

    Ach, da lässt sich bestimmt noch was zaubern mit der limits.h 🙄



  • DirkB schrieb:

    [Klugscheiss]
    Das ist aber nicht portabel, denn wer weiß schon wie groß ein int (danach wurde ja gefragt) auf dem jeweiligem System ist.
    [\Klugscheiss]

    Naja, dann kann man das zumindest mit Multiplikationen machen - die sind idR schneller zu haben:

    unsigned stellen(unsigned x) {
      unsigned n = 2;
      unsigned f = 10;
    
      if(x < 10) return 1;
      /* Overflow vermeiden */
      x /= 10;
    
      while(f <= x) {
        f *= 10;
        ++n;
      }
    
      return n;
    }
    

    Damit kriege ich gegenüber der Divisionsschleife einen Geschwindigkeitsgewinn von knapp 50%.

    Ab 64-Bit-Integern lohnt es sich auch, Abkürzungen zu nehmen. Beispielsweise kriege ich mit

    #include <limits.h>
    
    unsigned stellen(unsigned x) {
      static unsigned const SQ_LIMIT = UINT_MAX >> (sizeof(unsigned) * CHAR_BIT / 2);
      unsigned n = 1;
      unsigned factor = 10;
      unsigned t = factor;
    
      if(x < 10) return 1;
      /* Overflow vermeiden */
      x /= 10;
    
      while(t <= SQ_LIMIT && (t = factor * factor) <= x) {
        factor = t;
        n <<= 1;
      }
    
      while(factor <= x) {
        ++n;
        factor *= 10;
      }
    
      return n + 1;
    }
    

    und gleichverteilter Stellenanzahl einen Geschwindigkeitsgewinn von etwa 25% gegenüber der einfachen Multiplikationsschleife oben. Merke, dass es sich dabei um gleichverteilte Stellenanzahl handelt, nicht um gleichverteilte Eingabewerte. Bei gleichverteilten Eingabewerten bis 264 ist mehr zu erwarten. Von der Laufzeitkomplexität her (gemessen an der Breite der Integer) ist da prinzipiell noch mehr zu holen; ich denke da etwa an

    unsigned stellen(unsigned x) {
      static unsigned const SQ_LIMIT = UINT_MAX >> (sizeof(unsigned) * CHAR_BIT / 2);
      unsigned n = 1;
      unsigned factor = 10;
      unsigned t = factor;
      unsigned y;
    
      if(x < 10) return 1;
      /* Overflow vermeiden */
      y = x / 10;
    
      while(t <= SQ_LIMIT && (t = factor * factor) <= y) {
        factor = t;
        n <<= 1;
      }
    
      return stellen(x / factor) + n;
    }
    

    Allerdings wird es wohl noch eine Weile dauern, bis Integer so breit sind, dass sich die Rekursion amortisiert.



  • cooky451 schrieb:

    Das düfte wohl so ziemlich die schlechteste Methode sein 😃

    Was gefällt dir nicht daran?

    Aber wie wärs damit?

    #include <stdio.h>
    
    unsigned num_length (int n)
    {
        if (n < 10)
            return 1;
        return 1 + num_length (n/10);
    }
    
    int main (void)
    {
        printf ("%d\n", num_length (1234));
    }
    


  • Schon interessant, dass heutige Compiler immer noch so schlecht sind, dass sogar eine Multiplikation schneller als eine Division ist.

    Z schrieb:

    Was gefällt dir nicht daran?

    Es ist blöd. Und Rekursion mag ich auch nicht :p



  • cooky451 schrieb:

    Schon interessant, dass heutige Compiler immer noch so schlecht sind, dass sogar eine Multiplikation schneller als eine Division ist.

    Der Prozessor kann schneller multiplizieren als dividieren. Was soll da ein schauer Compiler gleichmachen? Er kann nur ein wenig entschärfen durch Multiplikation gefolgt von shift und evtl einem bedingten Bit statt der Division, wenn die Division entschieden langsamer auf dem Prozessor ist. Das machen sie schon lange.



  • Was soll die CPU auch machen?

    Nehmt euch ein Blatt Papier:
    3 * 7 = ?
    3 / 7 = ?

    Okay, der Mathe-Coprozessor könnte aus der Multiplkation eine Addition bauen und aus der Division eine Subtraktion. Da sollten die Zeiten dann fast gleich sein.

    MfG f.-th.



  • f.-th. schrieb:

    Was soll die CPU auch machen?

    Nehmt euch ein Blatt Papier:
    3 * 7 = ?
    3 / 7 = ?

    Okay, der Mathe-Coprozessor könnte aus der Multiplkation eine Addition bauen und aus der Division eine Subtraktion. Da sollten die Zeiten dann fast gleich sein.

    MfG f.-th.

    Sei 0<=x<100 und ich stelle mir einen Prozessor vor, der das kleine 100x100 mit seinem MUL-Befehl schnell schafft.
    Statt

    y=x/7; //teure Division
    

    schreibe ich

    y=x*14; //y würde in zwei Registern liegen
    y+=15; 
    if(x>55) y+=15;
    y/=100; //keine Division, nur shift
    

    oder

    y=(x*14+x*3/10)/100
    

    oder sowas.
    Da die 7 zur Compilezeit feststeht, kann auch der Compiler so einen Trick herausknobeln. Mein Trick sieht noch nicht hübsch aus, das geht bestimmt noch besser.

    http://www.codeproject.com/KB/cs/FindMulShift.aspx?display=Mobile





  • Man kann schon davon ausgehen, dass der Compiler bei zur Compilezeit bekanntem Divisor keine Division in der Hardware macht, sondern sie durch Multiplikationen und Bitshifts ersetzt. Trotzdem ist die Berechnung natürlich langsamer als eine einfache Multiplikation.


  • Mod

    seldon schrieb:

    Man kann schon davon ausgehen, dass der Compiler bei zur Compilezeit bekanntem Divisor keine Division in der Hardware macht, sondern sie durch Multiplikationen und Bitshifts ersetzt. Trotzdem ist die Berechnung natürlich langsamer als eine einfache Multiplikation.

    Davon würde ich nicht ausgehen.


Anmelden zum Antworten