C で整数値の Log2 を正確に計算するにはどうすればよいですか?

C で整数値の Log2 を計算する正しい方法

C 標準ライブラリには、浮動小数点の log メソッドのみがあります。ただし、log メソッドは、式 Floor(2log(index)) を使用してバイナリ ツリー内のインデックスのレベルを見つけるためによく使用されます。

一般的なアプローチは、int targetlevel = int(log(index)/log(2)) を使用することです。ただし、このアプローチではエッジ要素 (値 2^n を持つ要素) の丸め誤差が発生し、予想される n.0 ではなく n-1.999999999999 が返される可能性があります。

正確な Log2 計算のためのソリューション

この問題を修正し、整数値の正確な log2 計算を保証するには、より良い方法は、bsr (ビット スキャン リバース) 命令を利用することです。 bsr は x86 および x86-64 プラットフォームで使用でき、符号なし整数で設定された最上位ビットの位置を返します。これは、正の整数の log2() と同等です。

bsr 命令を利用する最適化された C コード スニペットは次のとおりです。

#include <stdint.h>

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

このコードは、インライン ASM を使用して bsr 命令を効率的に呼び出し、整数の正確な log2 計算を提供します。

以上がC で整数値の Log2 を正確に計算するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。