Weg, um die Anzahl der Ziffern in einem Int zu erhalten?

386

Gibt es eine bessere Möglichkeit, die Länge eines Int zu ermitteln als diese Methode?

int length = String.valueOf(1000).length();
fnst
quelle
7
Definieren Sie bitte die Länge eines Int.
Tom
24
Ich denke, er möchte die Ziffern in der Zahl zählen.
Alberto Zaccagni
3
Die Antworten, die die Leute Ihnen geben, sind richtig ... sie geben Ihnen die Länge Ihres int an, ohne es in eine Zeichenfolge umzuwandeln ... aber warum möchten Sie es nicht in eine Zeichenfolge konvertieren? Ist es eine Geschwindigkeitssache? Wenn ja, bin ich nicht davon überzeugt, dass diese Methoden schneller sein werden ... vielleicht möchten Sie einige Tests durchführen (oder entscheiden, ob es überhaupt darauf ankommt)
Beska
3
@ptomli hexadezimale Ziffern sind immer noch Ziffern, nur in einem anderen Basissystem.
Mark Pim
2
@Ptomli Sicher, aber sowohl in der Integer.toString-Funktion als auch in der allgemeinen Konversation ist die Dezimalzahl die Standardeinstellung. Wenn die Bank mir sagt: "Schreiben Sie den Betrag Ihres Schecks in dieses Feld", frage ich sie nicht, ob ich ihn in Dezimal, Hex oder Oktal schreiben soll. Wir gehen von einer Dezimalzahl aus, sofern im Kontext nichts anderes angegeben oder gefordert ist.
Jay

Antworten:

349

Ihre String-basierte Lösung ist vollkommen in Ordnung, es gibt nichts "Unordentliches". Sie müssen erkennen, dass Zahlen mathematisch gesehen weder eine Länge noch Ziffern haben. Länge und Ziffern sind beide Eigenschaften einer physischen Darstellung einer Zahl in einer bestimmten Basis, dh einer Zeichenfolge.

Eine logarithmusbasierte Lösung macht (einige) die gleichen Dinge wie die String-basierte intern und wahrscheinlich (unwesentlich) schneller, weil sie nur die Länge erzeugt und die Ziffern ignoriert. Aber ich würde es nicht als klarer in der Absicht betrachten - und das ist der wichtigste Faktor.

Michael Borgwardt
quelle
54
+1 für die Absicht des Codes bei der Auswahl eines Weges zur Lösung eines Problems zu
berücksichtigen
5
Datenpunkt: Auf meinem Computer scheint die Protokollmethode knapp doppelt so schnell zu laufen wie die Methoden für die Zeichenfolgenlänge. Ich würde das nicht als unbedeutend bezeichnen, wenn die Methode häufig oder in einem zeitkritischen Codeabschnitt aufgerufen wird.
CPerkins
1
Siehe meinen Benchmark-Unit-Test unten (der möglicherweise auch fehlerhaft ist, ich bin kein Benchmark-Experte). Bei einer großen Anzahl von Läufen (100 000 000) beträgt die Geschwindigkeit auf meiner Maschine 11 bis 8 Sekunden und ist kaum doppelt so hoch.
Jean
5
@ CPerkins. Vorzeitige Optimierung. Du kennst das Spiel.
Michael Borgwardt
11
Einige (ziemlich späte) Ergänzungen: Es funktioniert möglicherweise nicht richtig für negative Werte, je nachdem, ob Sie erwarten, dass das "-" eine Ziffer ist oder nicht. Durch Hinzufügen Math.abs()wird dies jedoch behoben.
YingYang
265

Der Logarithmus ist dein Freund:

int n = 1000;
int length = (int)(Math.log10(n)+1);

NB: nur gültig für n> 0.

Dmitry Brant
quelle
2
Und ist das schneller oder besser als mit meiner Variante?
Am
+1 Du hast mich um eine Sekunde geschlagen und deine Antwort war richtig, wo meine leicht abweicht. Beachten Sie jedoch, dass sich der Compiler aufgrund einer fehlenden Besetzung von int
Dirk
2
@ Tom Warum sollten Sie annehmen, dass es teuer ist? Man könnte annehmen, dass der mathematische Co-Prozessor es ausführen würde, so dass es nahe an der Geschwindigkeit einer Addition liegen könnte. Selbst wenn Java den Co-Prozessor jetzt nicht verwendet, ist es eine gute Annahme, dass es ... (Wir werden Ihre noch ungebildete Implikation, dass Java langsam ist, einfach ignorieren, weil Sie wahrscheinlich nicht an Beweisen interessiert sind - oder wenn Sie wäre , würde Sie gehen shootout.alioth.debian.org und für sich selbst herausfinden)
Bill K
8
Funktioniert ... es sei denn, der Wert, den Sie überprüfen, ist = 0, was zu ungeraden Ergebnissen führt (-2147483647). Math.log10 API: "Wenn das Argument eine positive Null oder eine negative Null ist, ist das Ergebnis eine negative Unendlichkeit."
Mujimu
2
+1 Präsentation einer Methode ohne Objektspeicherzuweisungen. Dies ist ein Muss, um die Wiederverwendung zu maximieren und GC-Sammlungen zu vermeiden.
Michael Wojcik
159

Der schnellste Ansatz: Teilen und Erobern.

Angenommen, Ihr Bereich liegt zwischen 0 und MAX_INT, dann haben Sie 1 bis 10 Stellen. Sie können dieses Intervall mit Teilen und Erobern mit bis zu 4 Vergleichen pro Eingabe erreichen. Zuerst teilen Sie [1..10] mit einem Vergleich in [1..5] und [6..10], und dann teilen Sie jedes Intervall der Länge 5 mit einem Vergleich in ein Intervall der Länge 3 und 2. Das Intervall der Länge 2 erfordert einen weiteren Vergleich (insgesamt 3 Vergleiche), das Intervall der Länge 3 kann in ein Intervall der Länge 1 (Lösung) und ein Intervall der Länge 2 unterteilt werden. Sie benötigen also 3 oder 4 Vergleiche.

Keine Divisionen, keine Gleitkommaoperationen, keine teuren Logarithmen, nur ganzzahlige Vergleiche.

Code (lang aber schnell):

if (n < 100000){
        // 5 or less
        if (n < 100){
            // 1 or 2
            if (n < 10)
                return 1;
            else
                return 2;
        }else{
            // 3 or 4 or 5
            if (n < 1000)
                return 3;
            else{
                // 4 or 5
                if (n < 10000)
                    return 4;
                else
                    return 5;
            }
        }
    } else {
        // 6 or more
        if (n < 10000000) {
            // 6 or 7
            if (n < 1000000)
                return 6;
            else
                return 7;
        } else {
            // 8 to 10
            if (n < 100000000)
                return 8;
            else {
                // 9 or 10
                if (n < 1000000000)
                    return 9;
                else
                    return 10;
            }
        }
    }

Benchmark (nach dem Aufwärmen der JVM) - Sehen Sie sich den folgenden Code an, um zu sehen, wie der Benchmark ausgeführt wurde:

  1. Basismethode (mit String.length): 2145 ms
  2. log10-Methode: 711 ms = 3,02-mal so schnell wie die Basislinie
  3. wiederholte Teilung: 2797 ms = 0,77-mal so schnell wie die Grundlinie
  4. Teilen und Erobern: 74 ms = 28,99-
    mal so schnell wie die Grundlinie

Vollständiger Code:

public static void main(String[] args)
throws Exception
{

    // validate methods:
    for (int i = 0; i < 1000; i++)
        if (method1(i) != method2(i))
            System.out.println(i);
    for (int i = 0; i < 1000; i++)
        if (method1(i) != method3(i))
            System.out.println(i + " " + method1(i) + " " + method3(i));
    for (int i = 333; i < 2000000000; i += 1000)
        if (method1(i) != method3(i))
            System.out.println(i + " " + method1(i) + " " + method3(i));
    for (int i = 0; i < 1000; i++)
        if (method1(i) != method4(i))
            System.out.println(i + " " + method1(i) + " " + method4(i));
    for (int i = 333; i < 2000000000; i += 1000)
        if (method1(i) != method4(i))
            System.out.println(i + " " + method1(i) + " " + method4(i));

    // work-up the JVM - make sure everything will be run in hot-spot mode
    allMethod1();
    allMethod2();
    allMethod3();
    allMethod4();

    // run benchmark
    Chronometer c;

    c = new Chronometer(true);
    allMethod1();
    c.stop();
    long baseline = c.getValue();
    System.out.println(c);

    c = new Chronometer(true);
    allMethod2();
    c.stop();
    System.out.println(c + " = " + StringTools.formatDouble((double)baseline / c.getValue() , "0.00") + " times as fast as baseline");

    c = new Chronometer(true);
    allMethod3();
    c.stop();
    System.out.println(c + " = " + StringTools.formatDouble((double)baseline / c.getValue() , "0.00") + " times as fast as baseline");

    c = new Chronometer(true);
    allMethod4();
    c.stop();
    System.out.println(c + " = " + StringTools.formatDouble((double)baseline / c.getValue() , "0.00") + " times as fast as baseline");
}


private static int method1(int n)
{
    return Integer.toString(n).length();
}
private static int method2(int n)
{
    if (n == 0)
        return 1;
    return (int)(Math.log10(n) + 1);
}
private static int method3(int n)
{
    if (n == 0)
        return 1;
    int l;
    for (l = 0 ; n > 0 ;++l)
        n /= 10;
    return l;
}
private static int method4(int n)
{
    if (n < 100000)
    {
        // 5 or less
        if (n < 100)
        {
            // 1 or 2
            if (n < 10)
                return 1;
            else
                return 2;
        }
        else
        {
            // 3 or 4 or 5
            if (n < 1000)
                return 3;
            else
            {
                // 4 or 5
                if (n < 10000)
                    return 4;
                else
                    return 5;
            }
        }
    }
    else
    {
        // 6 or more
        if (n < 10000000)
        {
            // 6 or 7
            if (n < 1000000)
                return 6;
            else
                return 7;
        }
        else
        {
            // 8 to 10
            if (n < 100000000)
                return 8;
            else
            {
                // 9 or 10
                if (n < 1000000000)
                    return 9;
                else
                    return 10;
            }
        }
    }
}


private static int allMethod1()
{
    int x = 0;
    for (int i = 0; i < 1000; i++)
        x = method1(i);
    for (int i = 1000; i < 100000; i += 10)
        x = method1(i);
    for (int i = 100000; i < 1000000; i += 100)
        x = method1(i);
    for (int i = 1000000; i < 2000000000; i += 200)
        x = method1(i);

    return x;
}
private static int allMethod2()
{
    int x = 0;
    for (int i = 0; i < 1000; i++)
        x = method2(i);
    for (int i = 1000; i < 100000; i += 10)
        x = method2(i);
    for (int i = 100000; i < 1000000; i += 100)
        x = method2(i);
    for (int i = 1000000; i < 2000000000; i += 200)
        x = method2(i);

    return x;
}
private static int allMethod3()
{
    int x = 0;
    for (int i = 0; i < 1000; i++)
        x = method3(i);
    for (int i = 1000; i < 100000; i += 10)
        x = method3(i);
    for (int i = 100000; i < 1000000; i += 100)
        x = method3(i);
    for (int i = 1000000; i < 2000000000; i += 200)
        x = method3(i);

    return x;
}
private static int allMethod4()
{
    int x = 0;
    for (int i = 0; i < 1000; i++)
        x = method4(i);
    for (int i = 1000; i < 100000; i += 10)
        x = method4(i);
    for (int i = 100000; i < 1000000; i += 100)
        x = method4(i);
    for (int i = 1000000; i < 2000000000; i += 200)
        x = method4(i);

    return x;
}

Wieder Benchmark:

  1. Basismethode (mit String.length): 2145 ms
  2. log10-Methode: 711 ms = 3,02-mal so schnell wie die Basislinie
  3. wiederholte Teilung: 2797 ms = 0,77-mal so schnell wie die Grundlinie
  4. Teilen und Erobern: 74 ms = 28,99-
    mal so schnell wie die Grundlinie

Bearbeiten: Nachdem ich den Benchmark geschrieben hatte, nahm ich einen kleinen Einblick in Integer.toString von Java 6 und stellte fest, dass es Folgendes verwendet:

final static int [] sizeTable = { 9, 99, 999, 9999, 99999, 999999, 9999999,
                                  99999999, 999999999, Integer.MAX_VALUE };

// Requires positive x
static int stringSize(int x) {
    for (int i=0; ; i++)
        if (x <= sizeTable[i])
            return i+1;
}

Ich habe es mit meiner Divide-and-Conquer-Lösung verglichen:

  1. Teilen und Erobern: 104ms
  2. Java 6-Lösung - iterieren und vergleichen: 406 ms

Meins ist ungefähr 4x so schnell wie die Java 6-Lösung.

Marian
quelle
7
das sieht gut aus Sie könnten es mit dem Operator ?: etwas kompakter schreiben, um mehr Akzeptanz zu erhalten
André Pareis
88
Sprechen Sie über vorzeitige Optimierung: D
Gordon Gustafson
2
Ich mag das! Wie wäre es mit einem Switch-Block anstelle von so verschachtelten If-Elses?
Kebman
2
Ich wusste nicht, dass all diese Anweisungen SO viel schneller wären, als das int in String zu konvertieren und dann .length aufzurufen. +1
Ogen
15
Mit dem ternären Operator werden 101 Zeichen erreicht:n<100000?n<100?n<10?1:2:n<1000?3:n<10000?4:5:n<10000000?n<1000000?6:7:n<100000000?8:n<1000000000?9:10
Jonathan Gawrych
13

Zwei Kommentare zu Ihrem Benchmark: Java ist eine komplexe Umgebung, was mit Just-in-Time-Kompilierung und Garbage Collection usw. zu tun hat. Um einen fairen Vergleich zu erhalten, wenn ich einen Benchmark durchführe, schließe ich immer: (a) die beiden Tests ein in einer Schleife, die sie 5 oder 10 Mal nacheinander ausführt. Sehr oft unterscheidet sich die Laufzeit beim zweiten Durchlauf durch die Schleife erheblich von der ersten. Und (b) Nach jedem "Ansatz" mache ich ein System.gc (), um zu versuchen, eine Garbage Collection auszulösen. Andernfalls generiert der erste Ansatz möglicherweise eine Reihe von Objekten, die jedoch nicht ausreichen, um eine Speicherbereinigung zu erzwingen. Der zweite Ansatz erstellt dann einige Objekte, der Heap ist erschöpft und die Speicherbereinigung wird ausgeführt. Dann wird der zweite Ansatz "aufgeladen", um den vom ersten Ansatz hinterlassenen Müll aufzunehmen. Sehr unfair!

Trotzdem hat keiner der oben genannten Punkte in diesem Beispiel einen signifikanten Unterschied gemacht.

Mit oder ohne diese Änderungen habe ich ganz andere Ergebnisse erzielt als Sie. Als ich dies ausführte, gab der toString-Ansatz Laufzeiten von 6400 bis 6600 Millis an, während der Log-Ansatz 20.000 bis 20.400 Millis überstieg. Anstatt etwas schneller zu sein, war der Log-Ansatz für mich dreimal langsamer.

Beachten Sie, dass die beiden Ansätze sehr unterschiedliche Kosten verursachen, sodass dies nicht völlig schockierend ist: Der toString-Ansatz erstellt viele temporäre Objekte, die bereinigt werden müssen, während der Protokollansatz eine intensivere Berechnung erfordert. Vielleicht besteht der Unterschied darin, dass toString auf einem Computer mit weniger Speicher mehr Speicherbereinigungsrunden erfordert, während auf einem Computer mit einem langsameren Prozessor die zusätzliche Berechnung des Protokolls schmerzhafter wäre.

Ich habe auch einen dritten Ansatz versucht. Ich habe diese kleine Funktion geschrieben:

static int numlength(int n)
{
    if (n == 0) return 1;
    int l;
    n=Math.abs(n);
    for (l=0;n>0;++l)
        n/=10;
    return l;           
}

Das lief zwischen 1600 und 1900 Millis - weniger als 1/3 des toString-Ansatzes und 1/10 des Log-Ansatzes auf meinem Computer.

Wenn Sie über ein breites Spektrum an Zahlen verfügen, können Sie diese weiter beschleunigen, indem Sie zunächst durch 1.000 oder 1.000.000 dividieren, um die Anzahl der Durchgänge durch die Schleife zu verringern. Damit habe ich nicht gespielt.

Jay
quelle
Haben Sie versucht, die Eingabe zu variieren? Die Hotspot-VM könnte dieses Diagramm andernfalls optimieren, was zu falschen Benchmarks führt, da jedes Mal dasselbe vorberechnete Element zurückgegeben wird.
Erik Aigner
11

Verwenden von Java

int nDigits = Math.floor(Math.log10(Math.abs(the_integer))) + 1;

Verwendung import java.lang.Math.*;am Anfang

Verwenden von C.

int nDigits = floor(log10(abs(the_integer))) + 1;

Verwendung inclue math.ham Anfang

Santosh
quelle
1
Nur zu Ihrer Information, wird zu unendlich führen, wenn dies der Fall the_integerist 0. Überprüfen Sie dies.
Erik Aigner
10

Ich kann noch keinen Kommentar hinterlassen, daher werde ich als separate Antwort posten.

Die logarithmusbasierte Lösung berechnet nicht die richtige Anzahl von Stellen für sehr große lange Ganzzahlen, zum Beispiel:

long n = 99999999999999999L;

// correct answer: 17
int numberOfDigits = String.valueOf(n).length();

// incorrect answer: 18
int wrongNumberOfDigits = (int) (Math.log10(n) + 1); 

Die logarithmusbasierte Lösung berechnet die falsche Anzahl von Ziffern in großen Ganzzahlen

launisch
quelle
Versuchen Sie stattdessen (int) (Math.log10 (n + j)), wobei j 10 - (n - n / 10 * 10) ist.
Erick Stone
8

Da die Anzahl der Ziffern in Basis 10 einer Ganzzahl nur 1 + abgeschnitten ist (log10 (Zahl)) , können Sie Folgendes tun:

public class Test {

    public static void main(String[] args) {

        final int number = 1234;
        final int digits = 1 + (int)Math.floor(Math.log10(number));

        System.out.println(digits);
    }
}

Bearbeitet, weil meine letzte Bearbeitung das Codebeispiel behoben hat, aber nicht die Beschreibung.

Dolch
quelle
Cool. aber ich denke es braucht abs (nummer) und auch "0" ist auch ein Sonderfall?
DmitryK
Ja. Wenn Sie das Zeichen berücksichtigen müssen, müssen Sie etwas wie 1 + (int) Math.floor (Math.log10 (Math.abs (Nummer))) + ((Nummer <0)? 1: 0)
Dirk
5
Das Math.floorist ein bisschen überflüssig, nicht wahr? Casting to intwird es trotzdem abrunden.
CompuChip
5

Marians Lösung für lange Typennummern (bis zu 9.223.372.036.854.775.807), falls jemand sie kopieren und einfügen möchte. In dem Programm, das ich für Zahlen geschrieben habe, waren bis zu 10000 viel wahrscheinlicher, also habe ich einen bestimmten Zweig für sie gemacht. Auf jeden Fall wird es keinen signifikanten Unterschied machen.

public static int numberOfDigits (long n) {     
    // Guessing 4 digit numbers will be more probable.
    // They are set in the first branch.
    if (n < 10000L) { // from 1 to 4
        if (n < 100L) { // 1 or 2
            if (n < 10L) {
                return 1;
            } else {
                return 2;
            }
        } else { // 3 or 4
            if (n < 1000L) {
                return 3;
            } else {
                return 4;
            }
        }           
    } else  { // from 5 a 20 (albeit longs can't have more than 18 or 19)
        if (n < 1000000000000L) { // from 5 to 12
            if (n < 100000000L) { // from 5 to 8
                if (n < 1000000L) { // 5 or 6
                    if (n < 100000L) {
                        return 5;
                    } else {
                        return 6;
                    }
                } else { // 7 u 8
                    if (n < 10000000L) {
                        return 7;
                    } else {
                        return 8;
                    }
                }
            } else { // from 9 to 12
                if (n < 10000000000L) { // 9 or 10
                    if (n < 1000000000L) {
                        return 9;
                    } else {
                        return 10;
                    }
                } else { // 11 or 12
                    if (n < 100000000000L) {
                        return 11;
                    } else {
                        return 12;
                    }
                }
            }
        } else { // from 13 to ... (18 or 20)
            if (n < 10000000000000000L) { // from 13 to 16
                if (n < 100000000000000L) { // 13 or 14
                    if (n < 10000000000000L) { 
                        return 13;
                    } else {
                        return 14;
                    }
                } else { // 15 or 16
                    if (n < 1000000000000000L) {
                        return 15;
                    } else {
                        return 16;
                    }
                }
            } else { // from 17 to ...¿20?
                if (n < 1000000000000000000L) { // 17 or 18
                    if (n < 100000000000000000L) {
                        return 17;
                    } else {
                        return 18;
                    }
                } else { // 19? Can it be?
                    // 10000000000000000000L is'nt a valid long.
                    return 19;
                }
            }
        }
    }
}
GEFÄNGNIS
quelle
Sollte der Titel dieser Frage in "Weg, um die Anzahl der Ziffern in einem int / long zu erhalten" geändert werden? (und fügte das 'lange' Tag hinzu)
JAIL
4

Ein weiterer String-Ansatz. Kurz und bündig - für jede ganze Zahl n.

int length = ("" + n).length();
ThisClark
quelle
Funktioniert nur für positive Ganzzahlen nund Null. Kann verwendet werden ("" + Math.abs(n)).length(), um die Länge einer negativen Ganzzahl zu ermitteln.
ThisClark
3

Kann ich es versuchen? ;)

basierend auf Dirks Lösung

final int digits = number==0?1:(1 + (int)Math.floor(Math.log10(Math.abs(number))));
DmitryK
quelle
3

Wie wäre es mit einfacher alter Mathematik? Teilen Sie durch 10, bis Sie 0 erreichen.

public static int getSize(long number) {
        int count = 0;
        while (number > 0) {
            count += 1;
            number = (number / 10);
        }
        return count;
    }
Sinista
quelle
1
Hast du es getestet? Sie wissen, dass es, auch wenn es aus menschlicher Sicht sinnvoll ist, mit der "Denkweise" der Maschine nicht so funktioniert, oder? --- Lassen Sie mich eines vorschlagen: Erstellen Sie ein Array mit zwei Millionen Zahlen, vorzugsweise Long.MAX_VALUEdem Fall mit der schlimmsten Komplexität Ihres Codes, und System.nanoTime()führen Sie einen Taktversuch gegen die Fälle mit der schlimmsten Komplexität der anderen Lösung durch. ++ Versuchen Sie es tatsächlich mit einem Array, das mit einem Zufallsgenerator gefüllt ist, der auf den Bereich von 0bis eingestellt Long.MAX_VALUEist, nur für den Test der "durchschnittlichen Komplexität". ++ Sie finden die Ergebnisse möglicherweise ... sehr schockierend.
XenoRo
@thelima Dies funktioniert nicht richtig für Null oder Negative, aber das ist ein kleiner Fehler. Das Prinzip sieht für mich richtig aus. Auf welches "schockierende" Ergebnis beziehen Sie sich?
Jay
Sagen wir einfach, dass Computer ... Nun ... sie teilen sich nicht gern. Und in Fällen, in denen große "Warteschlangen" mit großen Zahlen verarbeitet werden müssen und jede Ziffer in jeder verarbeiteten Zahl eine Unterteilung erfordert ... Nun ... Dinge "werden sehr langsam, sehr schnell" ... Wenn Sie meine fangen Bedeutung ... --- Aus diesem Grund sehen Sie viele der Antworten hier mit Codes, die auf Test und Vergleich mit jeder Dezimalstelle basieren, wobei 'if's' anstelle von Divisionen verwendet werden: Wenn es nicht schneller ist, behält es zumindest den größten Teil seiner Geschwindigkeit bei von seinen schlimmsten Fällen. --- Machen Sie einen Test zwischen der Verwendung von Divisionen und Logarithmus auf großen Zahlen ...
XenoRo
@ TheLima wovon redest du? Für eine wird int,diese Schleife maximal 11 Mal ausgeführt. Haben Sie Beweise für Ihre Behauptungen?
Marquis von Lorne
@EJP Aus Hardware-Sicht ist die Division ein iterativer Prozess. Der schnellste mir bekannte Divisionsalgorithmus ist radix4, der 4 Bits pro Iteration generiert. Eine 32-Bit-Teilung benötigt also mindestens 8 Iterationen. Multiplikationen können beispielsweise parallel durchgeführt und auch in einfachere Multiplikationen unterteilt werden. entweder bis auf Bitebene (erfordert nur 5 Operationen) oder mit teilweiser Aufschlüsselung plus einer Nachschlagetabelle am Ende (Kompromiss zwischen klassischer Größe und Geschwindigkeit). Es geht nicht nur darum, "wie viele Iterationen"; Das Problem mit Divisionen liegt darin, "was jede Iteration auf Hardwareebene impliziert / tut"
XenoRo
2

Marians Lösung, jetzt mit Ternary:

 public int len(int n){
        return (n<100000)?((n<100)?((n<10)?1:2):(n<1000)?3:((n<10000)?4:5)):((n<10000000)?((n<1000000)?6:7):((n<100000000)?8:((n<1000000000)?9:10)));
    }

Weil wir können.

Benutzer wurde nicht gefunden
quelle
2
Das ist schwer zu lesen. Fügen Sie möglicherweise Leerzeichen und / oder Zeilenumbrüche hinzu.
michaelb958 - GoFundMonica
Aber verdammt ist es tragbar!
Trevor Rudolph
1

Neugierig habe ich versucht, es zu vergleichen ...

import org.junit.Test;
import static org.junit.Assert.*;


public class TestStack1306727 {

    @Test
    public void bench(){
        int number=1000;
        int a= String.valueOf(number).length();
        int b= 1 + (int)Math.floor(Math.log10(number));

        assertEquals(a,b);
        int i=0;
        int s=0;
        long startTime = System.currentTimeMillis();
        for(i=0, s=0; i< 100000000; i++){
            a= String.valueOf(number).length();
            s+=a;
        }
        long stopTime = System.currentTimeMillis();
        long runTime = stopTime - startTime;
        System.out.println("Run time 1: " + runTime);
        System.out.println("s: "+s);
        startTime = System.currentTimeMillis();
        for(i=0,s=0; i< 100000000; i++){
            b= number==0?1:(1 + (int)Math.floor(Math.log10(Math.abs(number))));
            s+=b;
        }
        stopTime = System.currentTimeMillis();
        runTime = stopTime - startTime;
        System.out.println("Run time 2: " + runTime);
        System.out.println("s: "+s);
        assertEquals(a,b);


    }
}

Die Ergebnisse sind:

Laufzeit 1: 6765
s: 400000000
Laufzeit 2: 6000
s: 400000000

Jetzt muss ich mich fragen, ob mein Benchmark tatsächlich etwas bedeutet, aber ich erhalte konsistente Ergebnisse (Variationen innerhalb einer ms) über mehrere Läufe des Benchmarks selbst ... :) Es sieht so aus, als wäre es sinnlos, dies zu optimieren ...


edit: Nach dem Kommentar von ptomli habe ich im obigen Code 'number' durch 'i' ersetzt und über 5 Läufe der Bank die folgenden Ergebnisse erhalten:

Laufzeit 1: 11500
s: 788888890
Laufzeit 2: 8547
s: 788888890

Laufzeit 1: 11485
s: 788888890
Laufzeit 2: 8547
s: 788888890

Laufzeit 1: 11469
s: 788888890
Laufzeit 2: 8547
s: 788888890

Laufzeit 1: 11500
s: 788888890
Laufzeit 2: 8547
s: 788888890

Laufzeit 1: 11484
s: 788888890
Laufzeit 2: 8547
s: 788888890
Jean
quelle
1
Was ist der Unterschied zwischen einer Verteilung von Zahlenwerten, beispielsweise von 0 bis zu einer Billion? :)
Ptomli
0

Was ist mit dieser rekursiven Methode?

    private static int length = 0;

    public static int length(int n) {
    length++;
    if((n / 10) < 10) {
        length++;
    } else {
        length(n / 10);
    }
    return length;
}
Jedi Dula
quelle
0

einfache Lösung:

public class long_length {
    long x,l=1,n;
    for (n=10;n<x;n*=10){
        if (x/n!=0){
            l++;
        }
    }
    System.out.print(l);
}
mikegh
quelle
0

Eine wirklich einfache Lösung:

public int numLength(int n) {
  for (int length = 1; n % Math.pow(10, length) != n; length++) {}
  return length;
}
VoidCatz
quelle
Ich würde eine einfache Zeile für eine Schleife mit einem leeren Körper nicht einfach nennen. Noch modulo eine Potenz von 10, um zu sehen, ob Sie das Gleiche zurückbekommen (können Sie nicht einfach einen Vergleich verwenden?).
Teepeemm
0

Oder stattdessen die Länge, die Sie überprüfen können, ob die Zahl größer oder kleiner als die gewünschte Zahl ist.

    public void createCard(int cardNumber, int cardStatus, int customerId) throws SQLException {
    if(cardDao.checkIfCardExists(cardNumber) == false) {
        if(cardDao.createCard(cardNumber, cardStatus, customerId) == true) {
            System.out.println("Card created successfully");
        } else {

        }
    } else {
        System.out.println("Card already exists, try with another Card Number");
        do {
            System.out.println("Enter your new Card Number: ");
            scan = new Scanner(System.in);
            int inputCardNumber = scan.nextInt();
            cardNumber = inputCardNumber;
        } while(cardNumber < 95000000);
        cardDao.createCard(cardNumber, cardStatus, customerId);
    }
}

}}

Szabi Zsoldos
quelle
Ich verstehe nicht Anscheinend beantworten Sie eine andere Frage.
Teepeemm
0

Ich habe noch keine multiplikationsbasierte Lösung gesehen. Logarithmus-, Divison- und String-basierte Lösungen werden für Millionen von Testfällen ziemlich unhandlich. Hier ist eine für ints:

/**
 * Returns the number of digits needed to represents an {@code int} value in 
 * the given radix, disregarding any sign.
 */
public static int len(int n, int radix) {
    radixCheck(radix); 
    // if you want to establish some limitation other than radix > 2
    n = Math.abs(n);

    int len = 1;
    long min = radix - 1;

    while (n > min) {
        n -= min;
        min *= radix;
        len++;
    }

    return len;
}

In Basis 10 funktioniert dies, weil n im Wesentlichen mit 9, 99, 999 verglichen wird ... da min 9, 90, 900 ... ist und n von 9, 90, 900 ... subtrahiert wird.

Leider ist dies nicht longnur durch Ersetzen jeder Instanz intaufgrund von Überlauf portierbar . Auf der anderen Seite, es passiert einfach so , es wird für Basen arbeitet 2 und 10 (aber nicht schlecht für die meisten anderen Basen). Sie benötigen eine Nachschlagetabelle für die Überlaufpunkte (oder einen Teilungstest ... ew)

/**
 * For radices 2 &le r &le Character.MAX_VALUE (36)
 */
private static long[] overflowpt = {-1, -1, 4611686018427387904L,
    8105110306037952534L, 3458764513820540928L, 5960464477539062500L,
    3948651115268014080L, 3351275184499704042L, 8070450532247928832L,
    1200757082375992968L, 9000000000000000000L, 5054470284992937710L,
    2033726847845400576L, 7984999310198158092L, 2022385242251558912L,
    6130514465332031250L, 1080863910568919040L, 2694045224950414864L,
    6371827248895377408L, 756953702320627062L, 1556480000000000000L,
    3089447554782389220L, 5939011215544737792L, 482121737504447062L,
    839967991029301248L, 1430511474609375000L, 2385723916542054400L,
    3902460517721977146L, 6269893157408735232L, 341614273439763212L,
    513726300000000000L, 762254306892144930L, 1116892707587883008L,
    1617347408439258144L, 2316231840055068672L, 3282671350683593750L,
    4606759634479349760L};

public static int len(long n, int radix) {
    radixCheck(radix);
    n = abs(n);

    int len = 1;
    long min = radix - 1;
    while (n > min) {
        len++;
        if (min == overflowpt[radix]) break;
        n -= min;
        min *= radix;

    }

    return len;
}
Jonathan Smith
quelle
0

Mit Design (basierend auf dem Problem). Dies ist eine Alternative von Teilen und Erobern. Wir definieren zuerst eine Aufzählung (wenn man bedenkt, dass es sich nur um ein Int ohne Vorzeichen handelt).

public enum IntegerLength {
    One((byte)1,10),
    Two((byte)2,100),
    Three((byte)3,1000),
    Four((byte)4,10000),
    Five((byte)5,100000),
    Six((byte)6,1000000),
    Seven((byte)7,10000000),
    Eight((byte)8,100000000),
    Nine((byte)9,1000000000);

    byte length;
    int value;

    IntegerLength(byte len,int value) {
        this.length = len;
        this.value = value;
    }

    public byte getLenght() {
        return length;
    }

    public int getValue() {
        return value;
    }
}

Jetzt definieren wir eine Klasse, die die Werte der Aufzählung durchläuft und die entsprechende Länge vergleicht und zurückgibt.

public class IntegerLenght {
    public static byte calculateIntLenght(int num) {    
        for(IntegerLength v : IntegerLength.values()) {
            if(num < v.getValue()){
                return v.getLenght();
            }
        }
        return 0;
    }
}

Die Laufzeit dieser Lösung entspricht der des Divide-and-Conquer-Ansatzes.

androider
quelle
Ein Teilen und Erobern würde in der Mitte beginnen und den verbleibenden Suchbereich halbieren. Dies hat eine lineare Laufzeit. Aber es spielt keine Rolle für nur 9 Vergleiche. Aber wird das nicht durcheinander bringen, wenn num>=Nine.getValue()?
Teepeemm
0

Man möchte dies meistens tun, weil man es "präsentieren" möchte, was meistens bedeutet, dass es schließlich explizit oder implizit "toString-ed" (oder auf andere Weise transformiert) werden muss; bevor es präsentiert werden kann (zum Beispiel gedruckt).

Wenn dies der Fall ist, versuchen Sie einfach, den erforderlichen "toString" explizit zu machen und die Bits zu zählen.

howToDeleteMyAccount
quelle
0

Wir können dies mit einer rekursiven Schleife erreichen

    public static int digitCount(int numberInput, int i) {
        while (numberInput > 0) {
        i++;
        numberInput = numberInput / 10;
        digitCount(numberInput, i);
        }
        return i;
    }

    public static void printString() {
        int numberInput = 1234567;
        int digitCount = digitCount(numberInput, 0);

        System.out.println("Count of digit in ["+numberInput+"] is ["+digitCount+"]");
    }
ericdemo07
quelle
0

Ich habe diese Funktion geschrieben, nachdem ich den Integer.javaQuellcode gesucht habe .

private static int stringSize(int x) {
    final int[] sizeTable = {9, 99, 999, 9_999, 99_999, 999_999, 9_999_999,
            99_999_999, 999_999_999, Integer.MAX_VALUE};
    for (int i = 0; ; ++i) {
        if (x <= sizeTable[i]) {
            return i + 1;
        }
    }
}
Shellhub
quelle
0

Ich sehe Leute, die String-Bibliotheken oder sogar die Integer-Klasse verwenden. Daran ist nichts auszusetzen, aber der Algorithmus zum Abrufen der Anzahl der Ziffern ist nicht so kompliziert. Ich verwende in diesem Beispiel ein Long, aber es funktioniert genauso gut mit einem Int.

 private static int getLength(long num) {

    int count = 1;

    while (num >= 10) {
        num = num / 10;
        count++;
    }

    return count;
}
Sameer Khanal
quelle
0

Keine String-API, keine Utils, keine Typkonvertierung, nur reine Java-Iteration ->

public static int getNumberOfDigits(int input) {
    int numOfDigits = 1;
    int base = 1;
    while (input >= base * 10) {
        base = base * 10;
        numOfDigits++;
    }
    return numOfDigits;
 }

Wenn Sie möchten, können Sie sich nach größeren Werten sehnen.

Sahil
quelle
-1
    int num = 02300;
    int count = 0;
    while(num>0){
         if(num == 0) break;
         num=num/10;
         count++;
    }
    System.out.println(count);
Kanakangi
quelle
Eine "Division durch 10" -Lösung wurde erstmals zwei Jahre zuvor von Sinista veröffentlicht.
Teepeemm
-1

Einfacher rekursiver Weg

int    get_int_lenght(current_lenght, value)
{
 if (value / 10 < 10)
    return (current_lenght + 1);
return (get_int_lenght(current_lenght + 1, value))
}

nicht getestet

Valérian Polizzi
quelle
3
Sie sollten es dann wahrscheinlich testen (und sicherstellen, dass es gültiges Java und richtig formatiert ist). Ein rekursiver "Division durch 10" -Ansatz wurde jedoch vor 3 Jahren von Jedi Dula veröffentlicht.
Teepeemm
-2

Sie könnten die Ziffern durch sukzessive Division durch zehn:

int a=0;

if (no < 0) {
    no = -no;
} else if (no == 0) {
    no = 1;
}

while (no > 0) {
    no = no / 10;
    a++;
}

System.out.println("Number of digits in given number is: "+a);
user1590262
quelle
Ein "Divide by 10" -Ansatz wurde erstmals vor 3 Jahren von Sinista veröffentlicht. Das ist der einzige Grund, warum ich mir vorstellen kann, dass Sie eine Ablehnung erhalten haben.
Teepeemm
-2

Geben Sie die Nummer ein und erstellen Sie eine Arraylist, und die while-Schleife zeichnet alle Ziffern in der auf Arraylist. Dann können wir die Größe des Arrays herausnehmen, die der Länge des von Ihnen eingegebenen ganzzahligen Werts entspricht.

ArrayList<Integer> a=new ArrayList<>();

while(number > 0) 
{ 
    remainder = num % 10; 
    a.add(remainder);
    number = number / 10; 
} 

int m=a.size();
dev
quelle
1
Außer dass Sie weder die ArrayList noch die Ziffern benötigen.
Marquis von Lorne
-2

Hier ist eine wirklich einfache Methode, die ich gemacht habe und die für jede Zahl funktioniert:

public static int numberLength(int userNumber) {

    int numberCounter = 10;
    boolean condition = true;
    int digitLength = 1;

    while (condition) {
        int numberRatio = userNumber / numberCounter;
        if (numberRatio < 1) {
            condition = false;
        } else {
            digitLength++;
            numberCounter *= 10;
        }
    }

    return digitLength; 
}

Die Art und Weise, wie es mit der Zahlenzählervariablen funktioniert, ist, dass 10 = 1 stelliges Leerzeichen. Zum Beispiel .1 = 1 Zehntel => 1 Stellen. Wenn Sie also haben, erhalten int number = 103342;Sie 6, da dies das Äquivalent von .000001 Leerzeichen zurück ist. Hat jemand einen besseren Variablennamen fürnumberCounter ? Ich kann mir nichts Besseres vorstellen.

Edit: Ich dachte nur an eine bessere Erklärung. Im Wesentlichen bewirkt diese while-Schleife, dass Sie Ihre Zahl durch 10 teilen, bis sie kleiner als eins ist. Wenn Sie etwas durch 10 teilen, verschieben Sie es im Wesentlichen um ein Zahlenfeld zurück. Teilen Sie es also einfach durch 10, bis Sie <1 für die Anzahl der Stellen in Ihrer Zahl erreichen.

Hier ist eine andere Version, die die Anzahl der Zahlen in Dezimalzahlen zählen kann:

public static int repeatingLength(double decimalNumber) {

    int numberCounter = 1;
    boolean condition = true;
    int digitLength = 1;

    while (condition) {
        double numberRatio = decimalNumber * numberCounter;

        if ((numberRatio - Math.round(numberRatio)) < 0.0000001) {
            condition = false;
        } else {
            digitLength++;
            numberCounter *= 10;
        }
    }
    return digitLength - 1;
}
Andrew Patterson
quelle
-3

Versuchen Sie, das int in eine Zeichenfolge zu konvertieren , und ermitteln Sie dann die Länge der Zeichenfolge . Das sollte die Länge des int bekommen .

public static int intLength(int num){
    String n = Integer.toString(num);
    int newNum = n.length();
    return newNum;
}
user5458400
quelle
Dies entspricht vollständig dem Originalcode. Und wird vermissen, wenn numbernegativ ist.
Teepeemm