18

整数の2進対数を見つけるための非常に高速な方法はありますか？たとえば、数値x = 52656145834278593348959013841835216159447547700274555627155488768が与えられた場合、そのようなアルゴリズムは215であるy = log（x、2）を見つける必要があります。xは常に2の累乗です。

問題は本当に単純なようです。必要なのは、最上位1ビットの位置を見つけることだけです。よく知られているメソッドFloorLogがありますが、特に非常に長いマルチワード整数の場合はそれほど高速ではありません。

最速の方法は何ですか？

4

8 に答える 8

8

簡単なハック:ほとんどの浮動小数点数表現は値を自動的に正規化します。つまり、ハードウェアで言及されている Christoffer Hammarströmのループを効果的に実行します。したがって、数値が FP 表現の指数範囲内にある場合は、単純に整数から FP に変換して指数を抽出するだけでうまくいくはずです。(あなたの場合、整数入力には複数の機械語が必要なため、変換で複数の「シフト」を実行する必要があります。)

于 2010-04-21T07:22:54.077 に答える
5

整数が a に格納されている場合uint32_t a[]、私の明らかな解決策は次のようになります。

  1. 線形検索を実行してa[]、最大値のゼロ以外のuint32_t値a[i]を見つけます (マシンがネイティブサポートを備えている場合は、その検索a[]を使用してテストします)。uint64_tuint64_t

  2. 少しいじるハックを適用して、ステップ 1 で見つけbたuint32_t値のバイナリログを見つけます。a[i]

  3. 評価し32*i+bます。

于 2010-04-19T14:49:48.363 に答える
2

答えは、実装または言語に依存します。多くの場合に役立つため、どの実装でも有効ビット数をデータとともに格納できます。計算する必要がある場合は、最上位ワード/リムとそのワードの最上位ビットを見つけます。

于 2010-04-20T04:23:12.633 に答える
1

事前に対数の配列を作成できます。これにより、log(N) までの対数値が検出されます。

#define N 100000
int naj[N];

naj[2] = 1;
for ( int i = 3; i <= N; i++ )
{
    naj[i] = naj[i-1];
    if ( (1 << (naj[i]+1)) <= i )
        naj[i]++;

}

配列 naj は対数値です。ここで、naj[k] = log(k) です。ログは2つに基づいています。

于 2016-10-21T21:55:08.280 に答える