Numero di cifre in un intero in Java

1. Introduzione

In questo rapido tutorial, esploreremo diversi modi per ottenere il numero di cifre in un numero intero in Java.

Analizzeremo anche questi diversi metodi e scopriremo quale algoritmo si adatterebbe meglio alla nostra situazione.

2. Numero di cifre in un intero

Per i metodi discussi qui, stiamo considerando solo numeri interi positivi. Se ci aspettiamo un input negativo, possiamo prima utilizzare Math.abs (numero) prima di utilizzare uno di questi metodi.

2.1. Soluzione basata su stringhe

Forse il modo più semplice per ottenere il numero di cifre in un numero intero è convertirlo in String e chiamare il metodo length () . Questo restituirà la lunghezza della rappresentazione String del nostro numero:

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

Tuttavia, questo potrebbe essere un approccio non ottimale, poiché questa istruzione implica l'allocazione di memoria per una stringa, per ogni valutazione . La JVM deve prima analizzare il nostro numero e copiare le sue cifre in una stringa separata ed eseguire anche una serie di operazioni diverse (come conservare copie temporanee, gestire conversioni Unicode ecc.).

Se abbiamo solo pochi numeri da valutare, allora possiamo chiaramente scegliere questa soluzione, perché la differenza tra questo e qualsiasi altro approccio sarà trascurabile anche per grandi numeri.

2.2. Approccio logaritmico

Per i numeri rappresentati in forma decimale, se prendiamo il loro log in base 10 e lo arrotondiamo per eccesso, otterremo il numero di cifre in quel numero:

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

Si noti che il registro 10 0 di qualsiasi numero non è definito. Quindi, se ci aspettiamo un input con valore 0 , possiamo controllare anche quello.

L'approccio logaritmico è significativamente più veloce dell'approccio basato su String in quanto non deve passare attraverso il processo di conversione dei dati. Si tratta solo di un calcolo semplice e diretto senza alcuna inizializzazione o loop di oggetti aggiuntivi.

2.3. Moltiplicazione ripetuta

In questo metodo, prenderemo una variabile temporanea (inizializzata a 1) e la moltiplicheremo continuamente per 10 finché non diventa maggiore del nostro numero. Durante questo processo, utilizzeremo anche una variabile di lunghezza che terrà traccia della lunghezza del numero:

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

In questo codice, la riga temp * = 10 equivale a scrivere temp = (temp << 3) + (temp << 1) . Poiché la moltiplicazione è solitamente un'operazione più costosa su alcuni processori rispetto agli operatori di turno, questi ultimi potrebbero essere un po 'più efficienti.

2.4. Divisione con poteri di due

Se conosciamo l'intervallo del nostro numero, possiamo utilizzare una variazione che ridurrà ulteriormente i nostri confronti. Questo metodo divide il numero per potenze di due (ad esempio 1, 2, 4, 8 ecc.):

Questo metodo divide il numero per potenze di due (ad esempio 1, 2, 4, 8 ecc.):

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;

Sfrutta il fatto che qualsiasi numero può essere rappresentato dall'aggiunta di potenze di 2. Ad esempio, 15 può essere rappresentato come 8 + 4 + 2 + 1, che sono tutte potenze di 2.

Per un numero di 15 cifre, avremmo fatto 15 confronti nel nostro approccio precedente, che abbiamo ridotto a solo 4 in questo metodo.

2.5. Dividere e conquistare

Questo è forse l'approccio più ingombrante rispetto a tutti gli altri descritti qui, ma inutile dire che questo è il più veloce perché non stiamo eseguendo alcun tipo di conversione, moltiplicazione, addizione o inizializzazione di oggetti.

Otteniamo la nostra risposta in sole tre o quattro semplici istruzioni if :

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; } } } }

Simile all'approccio precedente, possiamo usare questo metodo solo se conosciamo l'intervallo del nostro numero.

3. Benchmarking

Ora che abbiamo una buona comprensione delle potenziali soluzioni, eseguiamo ora un semplice benchmarking di tutti i nostri metodi utilizzando Java Microbenchmark Harness (JMH).

La tabella seguente mostra il tempo medio di elaborazione di ciascuna operazione (in nanosecondi):

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

La soluzione basata su String , che è la più semplice, è anche l'operazione più costosa, poiché questa è l'unica che richiede la conversione dei dati e l'inizializzazione di nuovi oggetti.

L'approccio logaritmico è significativamente più efficiente rispetto alla soluzione precedente, poiché non comporta alcuna conversione dei dati. Inoltre, essendo una soluzione a linea singola, può essere una buona alternativa all'approccio basato su stringhe .

La moltiplicazione ripetuta implica una semplice moltiplicazione, proporzionalmente alla lunghezza del numero; ad esempio, se un numero è lungo quindici cifre, questo metodo comporterà quindici moltiplicazioni.

Tuttavia, il metodo successivo sfrutta il fatto che ogni numero può essere rappresentato da potenze di due (l'approccio è simile al BCD) e riduce lo stesso a 4 operazioni di divisione, quindi è ancora più efficiente del primo.

Infine, come possiamo dedurre, l'algoritmo più efficiente è l'implementazione dettagliata di Divide and Conquer , che fornisce la risposta in sole tre o quattro semplici istruzioni if. Possiamo usarlo se abbiamo un ampio set di dati di numeri che dobbiamo analizzare.

4. Conclusione

In questo breve articolo, abbiamo delineato alcuni dei modi per trovare il numero di cifre in un numero intero e abbiamo confrontato l'efficienza di ciascun approccio.

E, come sempre, puoi trovare il codice completo su GitHub.