C で整数対数関数を実装するにはどうすればよいですか?

C の整数対数関数

C では、標準ライブラリは浮動小数点数を操作する対数関数を提供します。ただし、バイナリ ツリーでインデックスを操作する場合や、整数の対数演算が必要なその他のシナリオでは、浮動小数点ログの使用が適切ではない可能性があります。

特に懸念される点の 1 つは、浮動小数点ログ メソッドが分数を返す可能性があることです。特定のエッジ要素の値 (2^n の値を持つ要素)。したがって、このような計算でログを使用すると、バイナリ ツリーのインデックスのレベルを決定しようとするときに誤った結果が生じる可能性があります。

この問題を回避するには、整数ベースの対数関数を利用できます。 x86 および x86-64 プラットフォームでは、bsr (ビット スキャン リバース) と呼ばれる組み込み命令を使用して、この機能を実現できます。この命令は、符号なし整数の最も高い設定ビットの位置を返します。

C または C で bsr を使用して整数 log2 関数を実装する方法の例を次に示します。

#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;
}

これ整数対数演算を実行するときに正確な結果を保証するために、浮動小数点ログの代わりに関数を使用できます。設定された最上位ビットの位置を返す bsr 命令を利用することで、実質的に log2() と同じ演算を実行します。

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