c++ - 数値を格納するために必要なビット数を計算する最速の方法は何ですか?

Question

いくつかのビット パッキングおよびアンパッキング ルーチンを最適化しようとしています。パッキングを行うには、整数値を格納するために必要なビット数を計算する必要があります。これが現在のコードです。

if (n == -1) return 32;
if (n == 0) return 1;
int r = 0;
while (n)
{
    ++r;
    n >>= 1;
}
return r;

Answer 1

移植性がなく、ほとんどの最新のアーキテクチャで利用可能なビット スキャン リバース オペコードを使用します。これは、Visual C++の組み込みとして公開されています。

ポータブルなことに、問題のコードはエッジケースの処理を必要としません。0 を格納するために 1 ビットが必要なのはなぜですか? いずれにせよ、問題の端は無視します。根性は次のように効率的に行うことができます。

if (n >> 16) { r += 16; n >>= 16; }
if (n >>  8) { r +=  8; n >>=  8; }
if (n >>  4) { r +=  4; n >>=  4; }
if (n >>  2) { r +=  2; n >>=  2; }
if (n - 1) ++r;

Answer 2

数値の整数対数底 2 (l = 最高ビット セット) を決定しようとしています。Sean Anderson の「Bit Twiddling Hacks」ページには、ループ内の明白なカウント ビットから、テーブル ルックアップを使用するバージョンまで、いくつかの方法が記載されています。その種の移植性が重要な場合、64 ビット int で動作するように、示されているメソッドのほとんどを少し変更する必要があることに注意してください。

• http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious

コンパイラの実装は、符号付きの値の操作をunsigned符号拡張する場合としない場合があるため、数値のバージョンで最高ビットセットを計算するために使用しているシフトを行う必要があることを確認してください。>>

Answer 3

あなたがやろうとしているのは、最も重要なビットを見つけることです。一部のアーキテクチャには、この目的のためだけに特別な命令があります。そうでない場合は、テーブル ルックアップ メソッドを使用します。

各要素が最上位ビットを識別する 256 エントリのテーブルを作成します。

数値の各バイトをループするか、いくつかの if ステートメントを使用して中断し、最上位のゼロ以外のバイトを見つけます。

残りはここからお任せします。

Answer 4

粒度を把握するには実行時間を確認する必要がありますが、私の推測では、一度に 4 ビットを実行してから、一度に 1 ビットに戻すと高速になると思います。ログ操作は、おそらく論理/ビット操作よりも遅くなります。

if (n < 0) return 32;
int r = 0;
while (n && 0x7FFFFFF0) {
  r+=4;
  n >>= 4; }
while (n) {
  r++;
  n >>= 1; }
return r;

Answer 5

線形検索の代わりに二分検索を実行します。

if ((n >> 16) != 0)
{
    r += 16;
    n >>= 16;
}

if ((n >> 8) != 0)
{
    r += 8;
    n >>= 8;        
}

if ((n >> 4) != 0)
{
    r += 4;
    n >>= 4;        
}

// etc.

ハードウェアにビット スキャン リバースがある場合は、ルーチンをアセンブリ言語で記述するとさらに高速になります。コードの移植性を維持するには、次のことができます

#ifdef ARCHITECTURE_WITH_BSR
   asm // ...
#else
   // Use the approach shown above
#endif

Answer 6

number_of_bits = log2(integer_number)

より高い整数に丸められます。