3

数値の 10 進数の桁数を数える必要があります (例: 1002 の場合は 4)。コードは膨大な数のセットに対して反復処理されるため、O(1) 時間の複雑さでこれを実行し、CPU 時間を大幅に節約したいと考えています。

私は2つの解決策を考え出しました：

  1. 数がゼロになるまでループで 10 で割ります。ループ回数が答えです。しかし、明らかに O(n) 時間です。
  2. log_base_10(num) + 1

質問: log10 は O(1) ソリューションですか? x86 マシンで glibc を使用してコードを実行しています。それは内部でどのように実装されていますか? そして、これに対するより良い解決策はありますか?

4

6 に答える 6

2

符号なし整数と Intel プラットフォーム (BSR 命令) を想定すると、設定された最上位ビットを取得できます。それからあなたは知っています：

2^i <= num < 2^(i+1)

のi最上位セット ビットですnum。そのため、単純なルックアップ テーブル ( でインデックス付けi) では、可能な 10 進数の数は 2 つに制限され、1 つの if だけで解決できます。

しかし、移植性のない最適化が必要なほど大きな数を本当に使用するのでしょうか?

于 2012-05-23T15:56:17.333 に答える
2

これは、Bit Twiddling Hacksのケースのように見えます

unsigned int v; // non-zero 32-bit integer value to compute the log base 10 of 
int r;          // result goes here

r = (v >= 1000000000) ? 9 : (v >= 100000000) ? 8 : (v >= 10000000) ? 7 : 
    (v >= 1000000) ? 6 : (v >= 100000) ? 5 : (v >= 10000) ? 4 : 
    (v >= 1000) ? 3 : (v >= 100) ? 2 : (v >= 10) ? 1 : 0;

「この方法は、入力が 32 ビット値に均一に分散されている場合にうまく機能します。これは、入力の 76% が最初の比較で捕捉され、21% が 2 番目の比較で捕捉され、2% が 3 番目の比較で捕捉されるなど (比較ごとに残りを 90% ずつ切り落とします。その結果、必要な操作は平均で 2.6 未満です。」

于 2012-05-23T15:56:53.460 に答える
1

二重計算が含まれ、10で割るとサイクルが遅くなる可能性があるため、この問題を解決するためにログを使用しません。メモリと事前計算のための時間を犠牲にして、いくつかの整数命令で答えが得られる場合があります。たとえば、10000までの数値の桁数を事前に計算します。

int num_digits[10000];
for (int i = 0; i < 10000; ++i) {
  if (i < 10) {
    num_digits[i] = 1;
  } else if (i < 100) {
    num_digits[i] = 2;
  } else if (i < 1000) {
    num_digits[i] = 3;
  }
}

そして今ここにあなたが約4つの整数演算で数の桁数を得る方法があります：

int get(int n) {
  int result = 0;
  while (n > 10000) {
    result += 4;
    n /= 10000;
  }
  return result + num_digits[n];
}

もちろんこれはスピードのために記憶を犠牲にしますが、私たちが知っているようにフリーランチはありません。

于 2012-05-23T15:48:37.590 に答える
1

あなたがする必要があるのは、次のとおりです。

1 + floor(log(N)/log(10))

(これは 0 では機能しません。浮動小数点数を入力すると、小数点の左側の桁数が返され、0.1 より大きい浮動小数点数でのみ機能します。)

ほぼ確実に、元の x86 ではなく、CPU がサポートする拡張機能に FPU 命令があります。log(N)ループで何度も評価することで、これをテストできます。

これは、数値が int または float として格納されていることを前提としています。ライブラリを使用して数値を可変長配列として格納している場合、ライブラリが配列の長さを事前に計算する場合は O(1) 時間であり (正しいこと)、それ以外の場合は O(N) 時間です (不適切なライブラリ)。 ）。

すべての float 操作と同様に、99-100、999-1000 などの遷移に本当に近い場合、精度が問題になる可能性があります。Steve Jessop がこの回答のコメントで指摘しているように、過大評価/過小評価が問題ないかどうかを判断できます必要なセマンティクスに。少し余裕があるとさえ言えるかもしれません。これらの遷移番号で何らかの理由でこれが失敗した場合は、N に 0.1 のようなものを加算/減算できます (それほど多くの番号はありません: 手動ですべてを自分でテストして、これが正しいかどうかを確認できます)。必要）。

于 2012-05-23T15:39:39.387 に答える
-2 
class NumberOfDigits{

    public static void main(String ar[]){
        int n=99;
        System.out.println(""+(1+Math.floor(Math.log10(n))));
    }
}
于 2020-07-16T09:25:13.757 に答える