c - ビット単位の演算子を使用して対数底 2 を計算する方法は?

Question

C で数値の底 2 の対数を計算する必要がありますが、数学ライブラリを使用できません。答えは正確である必要はなく、最も近い int にします。私はそれについて考えましたが、while ループを使用して、数値が 2 未満になるまで数値を 2 で割り続け、反復回数を維持できることはわかっていますが、これはビットごとの演算子を使用して可能ですか?

Answer 1

すでに abamert によって回答されていますが、より具体的には、次のようにコーディングします。

Log2(x) = result
while (x >>= 1) result++;   

Answer 2

シフトをビット単位の演算子と見なすと、これは簡単です。

連続して 2 で除算する方法は既にご存じでしょう。

x >> 1x / 2C の符号なし整数と同じです。

これを高速化する必要がある場合は、「分割統治」を行うことができます。たとえば、0 になるまで一度に 4 ビットずつシフトし、その後戻って最後の 4 ビットを確認します。つまり、それぞれ 63 回ではなく、最大 16 回のシフトと 19 回の比較を意味します。最新の CPU で実際に高速であるかどうかは、テストしないとわかりません。そして、これをさらに一歩進めて、最初に 16 のグループを実行し、次に 4、次に 1 のグループを実行することができます。おそらくここでは役に立ちませんが、1024 ビットの整数がいくつかある場合は、検討する価値があるかもしれません。