Integer: 2 Fragen



  • Moin,
    ich habe zwei Fragen zu dem Datentyp Integer:
    1. eine char eindet doch auf \0, ein Integer auch?
    2. Wie kann man die Anzahl einer Zahl errechnen? Also wenn ich z.B. eine int mit dem Wert 46450 habe, soll das Ergebnis 5 sein, weil die Zahl hat 5 Zaichen.

    Bin neu in C++ (und im Programmmieren), Buch ist aber bestellt 😃

    Bis dann



  • Integer234 schrieb:

    Moin,
    ich habe zwei Fragen zu dem Datentyp Integer:
    1. eine char eindet doch auf \0, ein Integer auch?

    Nein, ein char endet nicht auf \0.
    Eine Zeichenfolge, d.h. eine Abfolge von mehreren chars, endet per Konvention auf \0 um das Ende zu markieren. Somit muss man die Größe nicht extra speichern.

    2. Wie kann man die Anzahl einer Zahl errechnen? Also wenn ich z.B. eine int mit dem Wert 46450 habe, soll das Ergebnis 5 sein, weil die Zahl hat 5 Zaichen.

    Ein int besteht nicht aus Zeichen. Ein int besteht intern aus Binär-Zahlen. Die Anzahl der binären Stellen erhälst du mit sizeof(int) * CHAR_BIT.
    Um die Anzahl der Ziffern zu bekommen musst du Mathematik nutzen, z.B. den Logarithmus.



  • Mathe 😕 ... Naja wie sagt man so schön: Wer schön sein will muss leiden...



  • std::to_string(13579).size();
    


  • Du kannst auch solange ganzzahlig durch 10 teilen, bis 0 rauskommt.

    Wenn du dabei mitzählst, wie oft du teilst, kennst du die Anzahl der Ziffer (in der Dezimaldarstellung).

    46450 / 10 = 4645   1
     4645 / 10 =  464   2
      464 / 10 =   46   3
       46 / 10 =    4   4 
        4 / 10 =    0   5 und fertig
    

  • Mod

    2. Wie kann man die Anzahl einer Zahl errechnen? Also wenn ich z.B. eine int mit dem Wert 46450 habe, soll das Ergebnis 5 sein, weil die Zahl hat 5 Zaichen.

    Du meinst die Anzahl ihrer Ziffern in Dezimalnotation? Am einfachsten ist es wohl mit dem geceilten Zehnerlogarithmus, std::log10 .

    Ich habe auch mal ein TMP-Tool dafür geschrieben, dass ich allerdings nirgends herumliegen habe.

    Edit: So einfach ist es dann doch nicht:

    for( unsigned i; std::cin >> i; )
    	if( i == 0 ) /// Spezialfall
    		std::cout << 1 << '\n';
    	else
    		std::cout << std::floor(std::log10(i) + 1) << '\n';
    

    Ist aber deutlich hässlicher als DirkB's Variante (und wird auch langsamer sein, was aber für dich kein Kriterium ist, oder?).



  • am einfachsten ist es mit meiner Version


  • Mod

    großbuchstaben schrieb:

    am einfachsten ist es mit meiner Version

    #include <cstdint>
    #include <initializer_list>
    
    std::uint64_t const pow10[]
    {
    	1,
    	10,
    	100,
    	1000,
    	10000,
    	100000,
    	1000000,
    	10000000,
    	100000000,
    	1000000000,
    	10000000000,
    	100000000000,
    	1000000000000,
    	10000000000000,
    	100000000000000,
    	1000000000000000,
    	10000000000000000,
    	100000000000000000,
    	1000000000000000000,
    	10000000000000000000u
    };
    
    unsigned digits( std::uint64_t v )
    {
    	unsigned t = (64 - __builtin_clzll(v)) * 1233 >> 12;
    	return t + 1 - (v < pow10[t]);
    }
    
    #include <iostream>
    
    int main()
    {
    	for( std::uint64_t i; std::cin >> i; )
    		std::cout << digits(i) << '\n';
    }
    

    Edit: Was solls, wenn schon denn schon.



  • @Arcoth
    Schöne Lösung.
    Wäre aber noch schöner wenn du sie kommentierst, damit auch Leute die den Trick nocht nicht kennen verstehen was abgeht.
    Und was daran einfacher sein soll als std::to_string(13579).size(); verstehe ich auch nicht.
    Performanter ja, cooler auch, aber einfacher sicher nicht.


  • Mod

    Performanter ja, cooler auch, aber einfacher sicher nicht.

    Ja, unpassend zitiert, da hast du völlig Recht. Aber der Trick ist simpel:

    unsigned digits( std::uint64_t v )
    {
        unsigned t = (64 - __builtin_clzll(v)) * 1233 >> 12; // (1)
        return t + 1 - (v < pow10[t]);                       // (2)
    }
    

    Die Idee ist, dass ich den Zehnerlogarithmus auf den Logarithmus zur Basis Zwei reduziere, den ich sehr performant berechnen kann.
    Der Zweierlogarithmus berechne ich mit der intrinsic __builtin_clzll (count leading zeros long long), welche die Anzahl der führenden Nullen in Binärnotation zurückgibt - und das ziehe ich von 64 ab, um den (um 1 erhöhten) Zweierlogarithmus zu bekommen.

    Dann wird der Zweierlogarithmus in (1) mit einer Konstante multipliziert, und zwar log(2)log(10)\frac{log(2)}{log(10)}, welche hier als 12332121233 * 2^{-12} gegeben ist. Allerdings ist das nicht immer präzise: Es muss in (2) noch getestet werden, ob v kleiner ist als die aktuelle Zehnerpotenz der der Logarithmus t entspricht, und wenn, wird natürlich 1 vom Ergebnis abgezogen (das ganze soll branch-less passieren!). Anschließend wird noch eins draufaddiert, weil nicht der Logarithmus, sondern die Anzahl der Stellen zurückgegeben werden soll.

    Das ganze ließe sich auch so schreiben:

    return t + (v >= pow10[t]);                       // (2)
    

    Den Trick gibt es auch bei Bit Twiddling Hacks, von wo ich ihn ursprünglich habe.

    Edit: Zur Erklärung der Konstante: Die wurde so gewählt dass sie einen möglichst kleinen Rundungsfehler enthält, und dabei nicht zu große Konstanten verwendet:
    log10(2)28=77.06477log_{10}(2) * 2^{8} = 77.064 \approx 77
    log10(2)210=308.255308log_{10}(2) * 2^{10} = 308.255 \approx 308
    log10(2)212=1233.01891233log_{10}(2) * 2^{12} = 1233.0189 \approx 1233
    log10(2)214=4932.07544932log_{10}(2) * 2^{14} = 4932.0754 \approx 4932
    log10(2)216=19728.319728log_{10}(2) * 2^{16} = 19728.3 \approx 19728
    Der kleinste Rundungsfehler liegt bei 2122^{12}, welches auch nicht zu groß ist.

    Edit²: Latex... muss öfter die Posts mal anschauen bevor ich absende.


Log in to reply