Javaの整数の桁数
1前書き
このクイックチュートリアルでは、Javaで
Integer
の桁数を取得する
さまざまな方法を探ります。
また、これらのさまざまな方法を分析し、どのアルゴリズムが私たちの状況に最も適しているかを判断します。
2
Integer
の桁数
ここで説明した方法では、正の整数のみを検討しています。否定的な入力があると思われる場合は、これらのメソッドを使用する前に、まず
Math.abs(number)
を使用してください。
2.1.
String
ベースのソリューション
Integer
の桁数を取得する最も簡単な方法は、おそらくそれを
String
に変換して
length()
メソッドを呼び出すことです。これは数値の
String
表現の長さを返します。
int length = String.valueOf(number).length();
-
しかし、このステートメントでは評価ごとに__Stringのメモリ割り当てが行われるため、これは最適とは言えない方法かもしれません。 (一時的なコピーの保存、Unicode変換の処理など)。
評価する数が少ない場合は、このソリューションを使用することをお勧めします。これは、他の方法との違いが大きい場合でも無視できるほどです。
2.2. 対数アプローチ
10進数で表現された数値について、10を底とする丸めをしてそれを切り上げると、その数値の桁数が得られます。
int length = (int) (Math.log10(number) + 1);
どんな数の
log〜10〜0
も定義されていないことに注意してください。したがって、値
0
の入力があると予想される場合は、それについても確認できます。
-
対数アプローチは、データ変換のプロセスを経る必要がないため、
String
ベースのアプローチよりもかなり高速です** オブジェクトの初期化やループを追加することなく、単純で直接的な計算が行われるだけです。
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など)。
この方法では、数を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として表すことができます。
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-microbenchmark-harness[Java Microbenchmark Harness(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結論
この短い記事では、
Integer
の桁数を見つける方法のいくつかを概説し、それぞれのアプローチの効率を比較しました。
そしていつものように、完全なコードhttps://github.com/eugenp/tutorials/tree/master/java-numbers[GitHubについて]を見つけることができます。