Javaの整数の桁数
1. 序章
このクイックチュートリアルでは、Javaの整数の桁数を取得するさまざまな方法について説明します。
また、さまざまな方法を分析して、それぞれの状況に最適なアルゴリズムを見つけます。
2. 整数の桁数
ここで説明する方法では、正の整数のみを考慮しています。 負の入力が予想される場合は、これらのメソッドを使用する前に、まず Math.abs(number)を使用できます。
2.1. Stringベースのソリューション
おそらく、 Integer の桁数を取得する最も簡単な方法は、それを String に変換し、 length()メソッドを呼び出すことです。 これにより、数値のString表現の長さが返されます。
int length = String.valueOf(number).length();
ただし、このステートメントには評価ごとの文字列のメモリ割り当てが含まれるため、これは最適ではないアプローチである可能性があります。 JVMは数値を解析し、その数字を別の文字列にコピーする必要があります ]だけでなく、他の多くの異なる操作(一時コピーの保持、Unicode変換の処理など)を実行します。
評価する数値が少ない場合は、このソリューションを使用できます。これは、このソリューションと他のアプローチとの違いは、数値が大きい場合でも無視できるためです。
2.2. 対数アプローチ
10進数で表される数値の場合、基数10でログを取得して切り上げると、その数値の桁数が取得されます。
int length = (int) (Math.log10(number) + 1);
任意の数のlog100が定義されていないことに注意してください。したがって、値 0 の入力が予想される場合は、それもチェックできます。
対数アプローチは、データ変換のプロセスを経る必要がないため、文字列ベースのアプローチよりも大幅に高速です。オブジェクトの初期化やループを追加することなく、単純で簡単な計算を行うだけです。
2.3. 繰り返し乗算
この方法では、一時変数(1に初期化)を取得し、数値より大きくなるまで10を継続的に乗算します。 このプロセスでは、 length 変数も使用します。これにより、数値の長さが追跡されます。
int length = 0;
long temp = 1;
while (temp <= number) {
length++;
temp *= 10;
}
return length;
このコードでは、 temp * = 10 書くのと同じです temp =(temp << 3)+(temp << 1) 。 乗算は通常、シフト演算子と比較して一部のプロセッサではコストのかかる操作であるため、後者の方が少し効率的です。
2.4. 2の累乗で割る
数値の範囲がわかっている場合は、比較をさらに減らすバリエーションを使用できます。 この方法では、数値を2の累乗で除算します(例: 1、2、4、8など):
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;
これは、2の累乗の加算によって任意の数を表すことができるという事実を利用しています。 たとえば、15は8 + 4 + 2 + 1として表すことができ、すべて2の累乗です。
15桁の数値の場合、以前のアプローチでは15の比較を行いますが、この方法では4つだけです。
2.5. 分割統治
ここで説明する他のすべてのアプローチと比較すると、これはおそらく最もかさばるアプローチです。 ただし、変換、乗算、加算、またはオブジェクトの初期化を実行していないため、最速でもあります。
たった3つか4つの簡単な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;
}
}
}
}
前のアプローチと同様に、この方法は、番号の範囲がわかっている場合にのみ使用できます。
3. ベンチマーク
考えられる解決策を十分に理解したので、 Javaマイクロベンチマークハーネス(JMH)を使用してメソッドの簡単なベンチマークを実行してみましょう。
次の表は、各操作の平均処理時間(ナノ秒単位)を示しています。
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
最も単純なStringベースのソリューションは、データ変換と新しいオブジェクトの初期化を必要とする唯一のソリューションであるため、最もコストのかかる操作でもあります。
対数アプローチは、データ変換を伴わないため、以前のソリューションよりも大幅に効率的です。 また、単一行のソリューションであるため、String-ベースのアプローチの優れた代替手段となる可能性があります。
繰り返し乗算には、数値の長さに比例した単純な乗算が含まれます。 たとえば、数値が15桁の場合、この方法には15回の乗算が含まれます。
ただし、次の方法では、すべての数値を2の累乗で表すことができるという事実を利用します(BCDと同様のアプローチ)。 同じ方程式を4つの除算演算に減らすため、前者よりもさらに効率的です。
最後に、推測できるように、最も効率的なアルゴリズムは、詳細な分割統治法の実装であり、3つまたは4つの単純なifステートメントで答えを提供します。 分析する必要のある数値のデータセットが大きい場合に使用できます。
4. 結論
この簡単な記事では、整数の桁数を見つける方法のいくつかを概説し、各アプローチの効率を比較しました。
いつものように、完全なコードはGitHubでから入手できます。