高速計算log 2

次にluaのソースコードを読んで、サプライズが増えました.例えば今日log 2(x)をすばやく計算する方法を見ました.コードは次のとおりです.

int luaO_log2 (unsigned int x) {
  static const lu_byte log_2[256] = {
    0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
    6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
    7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
    7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
    8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
    8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
    8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
    8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8
  };
  int l = -1;
  while (x >= 256) { l += 8; x >>= 8; }
  return l + log_2[x];
}

考えも素朴で、整数を2^nの形に変換してnを求めればいいのです.例えば256は2^8なので、ここでは配列log_2[256]=8であり、それらが2^nに変換されない数も近似的に計算される.例えば255では256=2^8であることが知られているが、128=2^7であるため、128と256の間の数は256に近似され、結果も8である.ロゴが見えます2[128]からlog_へ2[255]はすべて8に等しい.
ここで誤差は1です.完全に無視できます.この数が256より大きい場合は、256を除算し、結果を8にすればよい.最後の誤差は依然として1である.
実はあなたもこのロゴを2の配列はより大きく設計されており,whileサイクルに入る必要がある条件では求めた数がより大きくなることが要求される.著者らは256推定において,実際の計算過程において256以上の数に対してlog 2を求めることが少なくなったことを考慮した.このlog_2の配列はもっと合理的に設計することができます.例えば、log_2[128]からlog_へ2[255]の間の数はすべて8にするのではなく、128に近いところの数を7にし、255に近いところを8にするが、これはさらに面倒な考えに陥り、例えばどこを8にし、どこを7にするかなどである.もともとは高速計算のための関数だったが、最後には面倒になり、必然的によくない.
最後に私がインターネットで素早くlog 2を計算する方法を検索したとき、Quake IIIの不思議なコードを見ました.Quake IIIは本当に不思議なエンジンで、勉強に値するコードがたくさん入っていて、luaのソースコードを読んでから次のステップはそれを読むことです.まず、log 2の計算方法を見てみましょう.

static const int debruijn[32] = {
     0,  1, 28,  2, 29, 14, 24,  3, 30, 22, 20, 15, 25, 17,  4,  8,
    31, 27, 13, 23, 21, 19, 16,  7, 26, 12, 18,  6, 11,  5, 10,  9
};
#define LOG2(X) (debruijn[((Uint32)(((X) & -(X)) * 0x077CB531U)) >> 27])

このコードを見て、私は本当にびっくりしておしっこをしました.まず私は(x)&(-x)の意味がxの末尾の0と初めて現れた1を取り出すことしか知らない.その他は一切不明です.最も不思議なのは、この中にmagic number 0 x 077 CB 531 Uがまた現れたことだ.前回Quake IIIで見たニュートン変換の初期値のmagic numberの時におしっこしました.今回は例外ではない.ネットでMatrix 67の説明を見たのはよかったが、よく見ていなかったので、しばらく待ってから見た.
Lua :lobject.c
Quake III:trickコード
Matrix 67:謎の定数復帰!0 x 077 CB 531で末尾0の個数を計算する