60

優れたプログラミング リソースである Bit Twiddling Hacksは、32 ビット整数の log2 を計算する次の方法を提案しています (こちら)。

#define LT(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n
static const char LogTable256[256] = 
{
    -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
    LT(4), LT(5), LT(5), LT(6), LT(6), LT(6), LT(6),
    LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7)
};

unsigned int v; // 32-bit word to find the log of
unsigned r;     // r will be lg(v)
register unsigned int t, tt; // temporaries
if (tt = v >> 16)
{
    r = (t = tt >> 8) ? 24 + LogTable256[t] : 16 + LogTable256[tt];
}
else 
{
    r = (t = v >> 8) ? 8 + LogTable256[t] : LogTable256[v];
}

と述べています

ルックアップ テーブル方式では、32 ビット値のログを見つけるのに約 7 回の操作しかかかりません。64 ビット量に拡張すると、約 9 回の操作が必要になります。

しかし、残念ながら、アルゴリズムを 64 ビット整数に拡張するために実際にどの方法を使用すべきかについての追加情報はありません。

この種の 64 ビット アルゴリズムがどのように見えるかについてのヒントはありますか?

4

9 に答える 9

86

組み込み関数は非常に高速ですが、真にクロスプラットフォームでコンパイラに依存しない log2 の実装にはまだ不十分です。したがって、誰かが興味を持っている場合に備えて、これは私が自分でトピックを調査しているときに到達した、最速で分岐のない、CPU 抽象化された DeBruijn のようなアルゴリズムです。

const int tab64[64] = {
    63,  0, 58,  1, 59, 47, 53,  2,
    60, 39, 48, 27, 54, 33, 42,  3,
    61, 51, 37, 40, 49, 18, 28, 20,
    55, 30, 34, 11, 43, 14, 22,  4,
    62, 57, 46, 52, 38, 26, 32, 41,
    50, 36, 17, 19, 29, 10, 13, 21,
    56, 45, 25, 31, 35, 16,  9, 12,
    44, 24, 15,  8, 23,  7,  6,  5};

int log2_64 (uint64_t value)
{
    value |= value >> 1;
    value |= value >> 2;
    value |= value >> 4;
    value |= value >> 8;
    value |= value >> 16;
    value |= value >> 32;
    return tab64[((uint64_t)((value - (value >> 1))*0x07EDD5E59A4E28C2)) >> 58];
}

次に小さい 2 の累乗に切り下げる部分は、Power-of-2 Boundariesから取得され、末尾のゼロの数を取得する部分はBitScanから取得されました((bb & -bb)そこにあるコードは、設定されている右端のビットを選び出します1 (値を次の 2 の累乗に切り捨てた後は必要ありません)。

ちなみに、32ビット実装は

const int tab32[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};

int log2_32 (uint32_t value)
{
    value |= value >> 1;
    value |= value >> 2;
    value |= value >> 4;
    value |= value >> 8;
    value |= value >> 16;
    return tab32[(uint32_t)(value*0x07C4ACDD) >> 27];
}

他の計算方法と同様に、log2 では入力値が 0 より大きい必要があります。

于 2012-07-09T15:55:28.340 に答える
59

GCCを使用している場合、この場合はルックアップテーブルは不要です。

GCCには、先行ゼロの量を決定するための組み込み関数が用意されています。

組み込み関数： 最上位ビット位置から開始して、xの先頭の0ビットの数を返します。xが0の場合、結果は未定義です。int __builtin_clz (unsigned int x)

したがって、次のように定義できます。

#define LOG2(X) ((unsigned) (8*sizeof (unsigned long long) - __builtin_clzll((X)) - 1))

そしてそれはどんなunsignedlonglongintでも機能します。結果は切り捨てられます。

x86およびAMD64の場合、GCCはそれをbsr命令にコンパイルするため、ソリューションは非常に高速です（ルックアップテーブルよりもはるかに高速です）。

実例：

#include <stdio.h>

#define LOG2(X) ((unsigned) (8*sizeof (unsigned long long) - __builtin_clzll((X)) - 1))

int main(void) {
    unsigned long long input;
    while (scanf("%llu", &input) == 1) {
        printf("log(%llu) = %u\n", input, LOG2(input));
    }
    return 0;
}

コンパイルされた出力：https ：//godbolt.org/z/16GnjszMs

于 2012-07-07T16:30:41.923 に答える
11

2 を底とする整数対数

これは、64 ビットの符号なし整数に対して行うことです。これは、2 を底とする対数の下限を計算します。これは、最上位ビットのインデックスに相当します。この方法は、常に log264 = 6 ステップで実行される展開されたループを使用するため、大きな数に対して非常に高速です。

基本的に、{ 0 ≤ k ≤ 5: 2^(2^k) } = { 2³², 2¹⁶, 2⁸, 2⁴, 2², 2¹ } = { 4294967296, 65536, 256 , 16, 4, 2, 1 } となり、減算された値の指数 k を合計します。

int uint64_log2(uint64_t n)
{
  #define S(k) if (n >= (UINT64_C(1) << k)) { i += k; n >>= k; }

  int i = -(n == 0); S(32); S(16); S(8); S(4); S(2); S(1); return i;

  #undef S
}

0 の無効な入力が与えられた場合、これは –1 を返すことに注意してください (これはイニシャル-(n == 0)がチェックしているものです)。で呼び出すことをまったく期待しない場合は、初期化子のn == 0代わりにat entry を関数にint i = 0;追加できます。assert(n != 0);

10 を底とする整数対数

底が 10 の整数対数は、同様に計算できます — log₁₀2⁶⁴ ≅ 19.2659... であるため、テストする最大の平方は 10¹⁶ です (注: これは、底が 10 の整数対数を達成する最速の方法ではありません。整数除算を使用するためです。より高速な実装は、指数関数的に増加する値を持つアキュムレータを使用し、アキュムレータと比較して、事実上一種の二分探索を行うことです。)

int uint64_log10(uint64_t n)
{
  #define S(k, m) if (n >= UINT64_C(m)) { i += k; n /= UINT64_C(m); }

  int i = -(n == 0);
  S(16,10000000000000000); S(8,100000000); S(4,10000); S(2,100); S(1,10);
  return i;

  #undef S
}
于 2014-07-15T01:59:46.387 に答える
5

これは、追加の一時変数を使用しない、非常にコンパクトで高速な拡張機能です。

r = 0;

/* If its wider than 32 bits, then we already know that log >= 32.
So store it in R.  */
if (v >> 32)
  {
    r = 32;
    v >>= 32;
  }

/* Now do the exact same thing as the 32 bit algorithm,
except we ADD to R this time.  */
if (tt = v >> 16)
  {
    r += (t = tt >> 8) ? 24 + LogTable256[t] : 16 + LogTable256[tt];
  }
else
  {
    r += (t = v >> 8) ? 8 + LogTable256[t] : LogTable256[v];
  }

これは s のチェーンで構築されたもので、ここifでも追加のテンポラリは使用されていません。最速ではないかもしれませんが。

  if (tt = v >> 48)
    {
      r = (t = tt >> 8) ? 56 + LogTable256[t] : 48 + LogTable256[tt];
    }
  else if (tt = v >> 32)
    {
      r = (t = tt >> 8) ? 40 + LogTable256[t] : 32 + LogTable256[tt];
    }
  else if (tt = v >> 16)
    {
      r = (t = tt >> 8) ? 24 + LogTable256[t] : 16 + LogTable256[tt];
    }
  else 
    {
      r = (t = v >> 8) ? 8 + LogTable256[t] : LogTable256[v];
    }
于 2012-07-07T15:56:24.497 に答える
2

アルゴリズムは基本的に、最上位の 1 ビットを含むバイトを見つけ、ルックアップでそのバイトを調べてバイトの対数を見つけ、それをバイトの位置に追加します。

以下は、32 ビット アルゴリズムのやや簡略化されたバージョンです。

if (tt = v >> 16)
{
    if (t = tt >> 8)
    {
        r = 24 + LogTable256[t];
    }
    else
    {
        r = 16 + LogTable256[tt];
    }
}
else 
{
    if (t = v >> 8)
    {
        r = 8 + LogTable256[t];
    }
    else
    {
        r = LogTable256[v];
    }
}

これは、同等の 64 ビット アルゴリズムです。

if (ttt = v >> 32)
{
    if (tt = ttt >> 16)
    {
        if (t = tt >> 8)
        {
            r = 56 + LogTable256[t];
        }
        else
        {
            r = 48 + LogTable256[tt];
        }
    }
    else 
    {
        if (t = ttt >> 8)
        {
            r = 40 + LogTable256[t];
        }
        else
        {
            r = 32 + LogTable256[ttt];
        }
    }
}
else
{
    if (tt = v >> 16)
    {
        if (t = tt >> 8)
        {
            r = 24 + LogTable256[t];
        }
        else
        {
            r = 16 + LogTable256[tt];
        }
    }
    else 
    {
        if (t = v >> 8)
        {
            r = 8 + LogTable256[t];
        }
        else
        {
            r = LogTable256[v];
        }
    }
}

元のサイズよりも優れていると思われる任意のサイズ タイプのアルゴリズムを考え出しました。

unsigned int v = 42;
unsigned int r = 0;
unsigned int b;
for (b = sizeof(v) << 2; b; b = b >> 1)
{
    if (v >> b)
    {
        v = v >> b;
        r += b;
    }
}

注: b = sizeof(v) << 2b を v のビット数の半分に設定します。ここでは、乗算の代わりにシフトを使用しました (単純に、そのように感じたからです)。

そのアルゴリズムにルックアップ テーブルを追加して高速化することもできますが、それは概念実証に過ぎません。

于 2012-07-07T15:42:55.103 に答える
0

これは、 2009 年 3 月 22 日の SPWorleyからのわずかに変更されたものです(詳細については、投稿を参照してください)。

double ff=(double)(v|1);
return ((*(1+(uint32_t *)&ff))>>52)-1023;  // assumes x86 endianness

補足: 一部のユーザーは、状況によってはコンパイルすると間違った結果になる可能性があると指摘しました。

于 2019-10-20T15:19:35.720 に答える