4

2 ^ 3〜2 ^ 4、2 ^ 4〜2 ^ 5などの範囲内にあるかどうかのように。返される数値は、指数自体（オフセットを差し引いたもの）になります。

どうすればこれを可能な限り迅速かつ効率的に行うことができますか？この関数は、速度に大きく依存するプログラムで頻繁に呼び出されます。これは私の現在のコードですが、forループを使用しているため非効率的です。

static inline size_t getIndex(size_t numOfBytes)
{
    int i = 3;
    for (; i < 32; i++) 
    {
        if (numOfBytes < (1 << i)) 
            return i - OFFSET;
    }
    return (NUM_OF_BUCKETS - 1);
}

どうもありがとうございます！

4

7 に答える 7

9

私が知る限り、あなたが求めているのは単にlog 2（n ）です。

ターゲットアーキテクチャにこれを実行できる命令がある場合は、不正行為を行ってインラインアセンブリを使用する価値があるかもしれません。ハードウェアサポートに関する多くの議論と情報については、「最初のセットを見つける」に関するWikipediaのエントリを参照してください。

于 2012-08-14T18:15:13.100 に答える
5

これを行う1つの方法は、1に設定されている最上位ビットを見つけることです。ただし、最悪の場合でもn回のチェックを行う必要があるため、これが効率的かどうかを考えています。

たぶん、2 ^ 16より大きいかどうかをチェックするバイナリ検索スタイルを実行できます。そうである場合は、2 ^ 24より大きいかどうかをチェックし（ここでは32ビットと想定）、そうでない場合は、2^20より大きいかどうかをチェックします。 、など...これはlog（n）チェックになりますが、ビットチェックと完全なintの比較の効率はわかりません。

どちらかでいくつかのパフォーマンスデータを取得できます。

于 2012-08-14T18:09:16.123 に答える
1

SeanEronAndersonの優れたBitTwiddlingHacksページで説明されているdeBruijnシーケンスを使用した特に効率的なアルゴリズムがあります。

uint32_t v; // find the log base 2 of 32-bit v
int r;      // result goes here

static const int MultiplyDeBruijnBitPosition[32] = 
{
  0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
  8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
};

v |= v >> 1; // first round down to one less than a power of 2 
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;

r = MultiplyDeBruijnBitPosition[(uint32_t)(v * 0x07C4ACDDU) >> 27];

分岐せずに13回の操作で動作します！

于 2012-08-14T18:22:51.063 に答える
1

あなたは基本的に計算しようとしています：floor(log2(x))

対数を2を底とし、次に床を取ります。

Cでこれを行う最も移植性の高い方法は、基数elogf()への対数を見つける関数を使用して、次のように調整することです。 log2(x) == logf(x) / logf(2.0)

ここで答えを参照してください：c / c ++でログbase（2）を書く方法

結果のfloat値をにキャストするだけの場合は、同時にint計算します。floor()

ただし、それが利用可能であり、使用できる場合はlog2()、浮動小数点数を計算する非常に高速な方法があります。logbf()

マニュアルページから：

   The inte-
   ger constant FLT_RADIX, defined in <float.h>, indicates the radix  used
   for  the  system's  floating-point  representation.  If FLT_RADIX is 2,
   logb(x) is equal to floor(log2(x)), except that it is probably faster.

http://linux.die.net/man/3/logb

浮動小数点数がどのように格納されるかを考えると、値floor(log2(x))が数値の一部であることがわかります。その値を抽出するだけで完了です。少しシフトしてビットマスキングを行い、指数（または技術的には「仮数」）からバイアスを差し引くと、それが得られます。floor(log2(x))任意のfloat値を計算するために可能な最速の方法x。

http://en.wikipedia.org/wiki/Single_precision

しかし、実際にlogbf()は結果をfloatに変換してから提供し、エラーを処理します。指数を整数として抽出する独自の関数を作成すると、わずかに高速になり、とにかく整数が必要になります。独自の関数を作成する場合は、Cunionを使用してfloat内のビットにアクセスする必要があります。ポインタを操作しようとすると、少なくともGCCでは、「型のパンニング」に関連する警告またはエラーが発生します。ご要望があれば、その方法について詳しく説明します。私は以前にこのコードをinline関数として書いたことがあります。

テストする数値の範囲が狭い場合は、数値を整数にキャストしてから、ルックアップテーブルを使用できます。

于 2012-08-14T18:37:31.833 に答える
1

浮動小数点表現を利用できます。

double n_bytes = numOfBytes

浮動小数点数は次のように表されるため、指数ビットを取得すると結果が得られます。

(-1)^S X (1. + M) X 2^E

ここで、S-符号M-仮数E-指数

マスクとシフトを作成するには、使用している浮動小数点型の正確なビットパターンについて読む必要があります。

CPU浮動小数点サポートがほとんどの作業を代行します。

さらに良い方法は、組み込み関数を使用することです。

double frexp (double x, int * exp );

浮動小数点表現

于 2012-08-14T18:53:26.157 に答える
0

これは、ハードウェア浮動小数点ユニットを備えたすべてのマシンで一般的に高速です。

((union { float val; uint32_t repr; }){ x }.repr >> 23) - 0x7f

それが行う唯一の仮定は、浮動小数点がIEEEであり、整数と浮動小数点のエンディアンが一致することです。これらは両方とも、基本的にすべての実世界のシステム（確かにすべての最新のシステム）に当てはまります。

編集：私が過去にこれを使用したとき、私はそれを大量に必要としませんでした。エリックは、floatに収まらないintに対しては間違った結果をもたらすと指摘しています。これを修正し、最大52ビット（特に、すべての32ビット正整数入力）の値をサポートする改訂版（おそらく低速ですが）は次のとおりです。

((union { double val; uint64_t repr; }){ x }.repr >> 52) - 0x3ff

xまた、正の（負ではないだけでなく、ゼロでもない）数値であると想定していることにも注意してください。が負の場合xは偽の結果が得られ、xが0の場合は、大きな負の結果が得られます（対数として負の無限大に近似）。

于 2012-08-14T23:09:39.993 に答える
0 
#include <Limits.h>  // For CHAR_BIT.
#include <math.h>    // For frexp.
#include <stdio.h>   // For printing results, as a demonstration.


// These routines assume 0 < x.


/*  This requires GCC (or any other compiler that supplies __builtin_clz).  It
    should perform well on any machine with a count-leading-zeroes instruction
    or something similar.
*/
static int log2A(unsigned int x)
{
    return sizeof x * CHAR_BIT - 1 - __builtin_clz(x);
}


/*  This requires that a double be able to exactly represent any unsigned int.
    (This is true for 32-bit integers and 64-bit IEEE 754 floating-point.)  It
    might perform well on some machines and poorly on others.
*/
static int log2B(unsigned int x)
{
    int exponent;
    frexp(x, &exponent);
    return exponent - 1;
}


int main(void)
{
    // Demonstrate the routines.
    for (unsigned int x = 1; x; x <<= 1)
        printf("0x%08x:  log2A -> %2d, log2B -> %2d.\n", x, log2A(x), log2B(x));

    return 0;
}
于 2012-08-15T00:28:20.537 に答える