C での対数計算 : 整数 Log2 の実装

C では、バイナリのレベルを決定するために整数 log2() 関数が必要になります。ツリー構造。ただし、エッジ要素が 2^n の値に近づくと懸念が生じ、浮動小数点対数計算で丸め誤差が生じる可能性があります。

この問題に対処するには、最新の x86 または x86 で bsr 命令を利用する効率的な解決策が必要です。 -64プラットフォーム。この命令は、符号なし整数内の設定された最上位ビットの位置を返します。これは log2() と同じです。

インライン ASM を使用して bsr を呼び出す C または C 関数を次に示します:

#include 
static inline uint32_t log2(const uint32_t x) {
  uint32_t y;
  asm ( "\tbsr %1, %0\n"
      : "=r"(y)
      : "r" (x)
  );
  return y;
}

この手法を活用すると、バイナリ ツリー操作の正確な整数 log2() 計算を取得でき、適切なインデックス付けとレベル決定に必要な精度を確保できます。