Anzahl der Stellen in einer Ganzzahl in Java

1. Einleitung

In diesem kurzen Tutorial werden wir verschiedene Möglichkeiten untersuchen, wie Sie die Anzahl der Stellen in einer Ganzzahl in Java ermitteln können.

Wir werden auch diese verschiedenen Methoden analysieren und herausfinden, welcher Algorithmus am besten in unsere Situation passt.

2. Anzahl der Stellen in einer Ganzzahl

Für die hier diskutierten Methoden berücksichtigen wir nur positive ganze Zahlen. Wenn wir eine negative Eingabe erwarten, können wir zuerst Math.abs (Zahl) verwenden, bevor wir eine dieser Methoden verwenden.

2.1. String- basierte Lösung

Der einfachste Weg, die Anzahl der Stellen in einer Ganzzahl zu ermitteln, besteht darin, sie in einen String zu konvertieren und die Methode length () aufzurufen . Dies gibt die Länge der String- Darstellung unserer Nummer zurück:

int length = String.valueOf(number).length();

Dies kann jedoch ein suboptimaler Ansatz sein, da diese Anweisung die Speicherzuweisung für einen String für jede Auswertung umfasst . Die JVM muss zuerst unsere Nummer analysieren und ihre Ziffern in eine separate Zeichenfolge kopieren und auch eine Reihe verschiedener Vorgänge ausführen (z. B. temporäre Kopien aufbewahren, Unicode-Konvertierungen durchführen usw.).

Wenn wir nur wenige Zahlen zu bewerten haben, können wir uns eindeutig für diese Lösung entscheiden - denn der Unterschied zwischen diesem und jedem anderen Ansatz wird selbst bei großen Zahlen vernachlässigbar sein.

2.2. Logarithmischer Ansatz

Wenn wir für die in Dezimalform dargestellten Zahlen ihr Protokoll in Basis 10 nehmen und aufrunden, erhalten wir die Anzahl der Ziffern in dieser Zahl:

int length = (int) (Math.log10(number) + 1);

Beachten Sie, dass log 10 0 einer beliebigen Nummer nicht definiert ist. Wenn wir also eine Eingabe mit dem Wert 0 erwarten , können wir dies ebenfalls überprüfen.

Der logarithmische Ansatz ist erheblich schneller als der String- basierte Ansatz, da keine Datenkonvertierung durchgeführt werden muss. Es handelt sich lediglich um eine einfache, unkomplizierte Berechnung ohne zusätzliche Objektinitialisierung oder Schleifen.

2.3. Wiederholte Multiplikation

Bei dieser Methode nehmen wir eine temporäre Variable (auf 1 initialisiert) und multiplizieren sie kontinuierlich mit 10, bis sie größer als unsere Zahl wird. Während dieses Vorgangs verwenden wir auch eine Längenvariable , die die Länge der Nummer verfolgt:

int length = 0; long temp = 1; while (temp <= number) { length++; temp *= 10; } return length;

In diesem Code entspricht die Zeilentemperatur * = 10 dem Schreiben von temp = (temp << 3) + (temp << 1) . Da die Multiplikation auf einigen Prozessoren im Vergleich zu Schichtoperatoren normalerweise kostspieliger ist, kann letzterer etwas effizienter sein.

2.4. Teilen mit Zweierpotenzen

Wenn wir den Bereich unserer Anzahl kennen, können wir eine Variation verwenden, die unsere Vergleiche weiter reduziert. Diese Methode teilt die Zahl durch Zweierpotenzen (z. B. 1, 2, 4, 8 usw.):

Diese Methode teilt die Zahl durch Zweierpotenzen (z. B. 1, 2, 4, 8 usw.):

int length = 1; if (number >= 100000000) { length += 8; number /= 100000000; } if (number >= 10000) { length += 4; number /= 10000; } if (number >= 100) { length += 2; number /= 100; } if (number >= 10) { length += 1; } return length;

Es nutzt die Tatsache aus, dass jede Zahl durch Addition von Potenzen von 2 dargestellt werden kann. Beispielsweise kann 15 als 8 + 4 + 2 + 1 dargestellt werden, die alle Potenzen von 2 sind.

Für eine 15-stellige Zahl würden wir in unserem vorherigen Ansatz 15 Vergleiche durchführen, die wir bei dieser Methode auf nur 4 reduziert haben.

2.5. Teilen und erobern

Dies ist vielleicht der umfangreichste Ansatz im Vergleich zu allen anderen hier beschriebenen, aber natürlich ist dieser der schnellste, da wir keine Art von Konvertierung, Multiplikation, Addition oder Objektinitialisierung durchführen.

Wir erhalten unsere Antwort in nur drei oder vier einfachen if- Aussagen:

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

Ähnlich wie beim vorherigen Ansatz können wir diese Methode nur verwenden, wenn wir den Bereich unserer Anzahl kennen.

3. Benchmarking

Nachdem wir die möglichen Lösungen gut verstanden haben, führen wir nun ein einfaches Benchmarking aller unserer Methoden mit dem Java Microbenchmark Harness (JMH) durch.

Die folgende Tabelle zeigt die durchschnittliche Verarbeitungszeit jeder Operation (in Nanosekunden):

Benchmark Mode Cnt Score Error Units Benchmarking.stringBasedSolution avgt 200 32.736 ± 0.589 ns/op Benchmarking.logarithmicApproach avgt 200 26.123 ± 0.064 ns/op Benchmarking.repeatedMultiplication avgt 200 7.494 ± 0.207 ns/op Benchmarking.dividingWithPowersOf2 avgt 200 1.264 ± 0.030 ns/op Benchmarking.divideAndConquer avgt 200 0.956 ± 0.011 ns/op

Die einfachste String- basierte Lösung ist auch die teuerste Operation - da dies die einzige ist, die Datenkonvertierung und Initialisierung neuer Objekte erfordert.

Der logarithmische Ansatz ist im Vergleich zur vorherigen Lösung wesentlich effizienter, da keine Datenkonvertierung erforderlich ist. Als einzeilige Lösung kann sie eine gute Alternative zum String- basierten Ansatz sein.

Die wiederholte Multiplikation beinhaltet eine einfache Multiplikation proportional zur Zahlenlänge. Wenn eine Zahl beispielsweise fünfzehn Stellen lang ist, umfasst diese Methode fünfzehn Multiplikationen.

Die nächste Methode nutzt jedoch die Tatsache, dass jede Zahl durch Zweierpotenzen dargestellt werden kann (der Ansatz ähnelt BCD) und reduziert sie auf 4 Divisionsoperationen, sodass sie noch effizienter als die erstere ist.

Wie wir schließen können, ist der effizienteste Algorithmus die ausführliche Divide and Conquer-Implementierung, die die Antwort in nur drei oder vier einfachen if-Anweisungen liefert. Wir können es verwenden, wenn wir einen großen Datensatz von Zahlen haben, die wir analysieren müssen.

4. Fazit

In diesem kurzen Artikel haben wir einige Möglichkeiten beschrieben, wie die Anzahl der Stellen in einer Ganzzahl ermittelt werden kann, und die Effizienz jedes Ansatzes verglichen.

Und wie immer finden Sie den vollständigen Code auf GitHub.