6

ビットカウントはいくつかの方法で行うことができます。セットビット反復子、アンセットビット反復子、ルックアップテーブルまたは並列カウントを使用した事前計算済みビット。私がウェブを検索して理解したように、未設定のビットが少ない場合は未設定のビット反復子が高速であり、反対の場合はビット反復子が設定されます。しかし、並列カウント、特に MIT HAKMEM (以下を参照) を使用する必要があるのはいつですか? おそらくルックアップテーブルよりも遅いですが、かなり速いようです。速度の点で、ビットを設定/設定解除するよりも常に優れていますか? 速度とメモリ以外にどちらを選択するかについて、他に考慮すべき点はありますか?

 int BitCount(unsigned int u) {
     unsigned int uCount;

     uCount = u - ((u >> 1) & 033333333333) - ((u >> 2) & 011111111111);
     return ((uCount + (uCount >> 3)) & 030707070707) % 63;
 }
4

4 に答える 4

5

なぜ1つのビットカウント方法を別の方法よりも選択するのですか？まあそれは本当にあなたのマシンとあなたが解決しようとしている問題に依存します。以下に示すすべての命令数は、基本的なRISCプロセッサのものであり、x86のようなより複雑な獣にうまく変換されない可能性があることに注意してください。

引用したHAKMEMアルゴリズムは13命令で実行されますが、モジュラス演算子のために非常に高速になる可能性は低くなります。目を見張ると、プロセッサがそれを利用できる場合に役立つ、かなり優れた命令レベルの並列性があるように見えます。

Bo Perssonが提示したアルゴリズムは非常に高速です（2 + 5*pop(x)命令）が、単語がまばらに入力されている場合に限ります。また、密集した単語で機能するように変更することもできます。また、ブランチが含まれており、重要な命令レベルの並列性はありません。

編集：テーブルルックアップメソッドも非常に高速ですが、メモリアクセスを行います。テーブル全体がL1キャッシュにある場合、それはおそらく最速のアルゴリズムの1つです。テーブルがキャッシュにない場合、それはほぼ確実に最も遅いものの1つです。

以下のアルゴリズムは、HAKMEMアルゴリズムの1つのバリエーションであり、ハッカーのたのしみの本に示されています（この種のものが好きな場合は、この本を強くお勧めします）。19命令で実行され、ブランチフリーです。また、除算は使用しませんが、乗算はあります。また、同じマスクを可能な限り再利用することで、レジスターを使用する方法も非常に経済的です。ここでは、私が見ることができる重要な命令レベルの並列性はまだありません。

int pop(unsigned x) {
  unsigned n;

  n = (x >> 1) & 0x77777777;
  x = x - n;
  n = (n >> 1) & 0x77777777;
  x = x - n;
  n = (n >> 1) & 0x77777777;
  x = x - n;
  x = (x + (x >> 4)) & 0x0F0F0F0F;
  x = x * 0x01010101;
  return x >> 24;
}

Hacker's Delightの本には、9-8-7ビット幅のフィールドまたは浮動小数点演算子を使用するためのさらに特殊なアルゴリズムもいくつか紹介されています。上で提示した分析のほとんどは、その本からも部分的に取得されていることに注意してください。

実際には、トラックにはたくさんの方法があり、特定の状況でどれが最適に機能するかを確認する唯一の方法は、測定して比較することです。私はこれがかなり定型的な答えであることを理解していますが、代わりにあなたのプロセッサとコンパイラを裏返しに知ることです。

于 2012-01-10T06:12:21.527 に答える
4

これは非常に単純ですが、いくつかのビットが設定されているだけで驚くほど高速です。

int popCount (U64 x) {
   int count = 0;
   while (x) {
       count++;
       x &= x - 1; // reset LS1B
   }
   return count;
}

Chess プログラミング wikiから: Brian Kernighan のやり方

于 2012-01-10T00:09:22.117 に答える
1

SSE4 をサポートする x86-CPU を使用している場合、すべての作業を行うための単一の命令が既にあります: POPCNT. インテル® SSE4 プログラミング・リファレンスを参照してください。(PDF、698KB)

別の注意: HAKMEM 169 のような並列アルゴリズムには条件分岐が含まれていません。これは大きな利点です。最新のプロセッサは条件付き分岐の方向を予測しますが、ランダムな分岐パターンには問題があります。予測ミスは非常にコストがかかります (コストは 100 命令に相当するものを超える場合があります)。パフォーマンスが重要な場合は、可変ループ回数や条件ステートメントを使用したループを避けることをお勧めします。詳細については：

また、Book Hackers Delightの推奨も 2 番目です。

于 2012-01-11T17:07:56.280 に答える
0

次のようなものはどうでしょう。

  1. 各未加工の単語 r から、「w = r - (r & 0x55555555)」としてペアマンジされた単語を計算します。ビットの各ペアは、そのペアに設定されたビット数 (0 ～ 2) を保持します。
  2. 次に、各ペアマンジド単語から、クワッドマンジド単語 `q = (w & 0x33333333) + ((w >> 2) & 0x33333333)` を計算します。セット ビットの各カルテットは、そのカルテット内のセット ビット数 (0 ～ 4) を保持します。
  3. quad-munged ワードを 2 つのグループで合計し、それぞれの合計 `s` から、octet-munged sum `o = (s & 0x0F0F0F0F) + ((s >> 4) & 0x0F0F0F0F)` を計算します。各オクテットは、両方の入力ワード (0 ～ 16) の対応するオクテットに設定されたビットの総数を保持します。
  4. オクテット変更された合計を 8 つのグループで合計し、各合計 `s` からハーフワード変更された合計 `h = (s & 0x00FF00FF) + ((s >> 8) & 0x00FF00FF)` を計算します。各ハーフワードには、全 16 入力ワード (0 から 256) の対応するハーフワードに設定されたビットの総数が含まれます。
  5. ハーフワードで変更された合計を 128 のグループで合計し、各合計 `s` から総和 `t = (s & 0x0000FFFF) + ((s >> 16) & 0xFFFF)` を計算します。これにより、1024 入力ワード (0 ～ 32768) のセット ビット数が保持されます。

単語ごとに 2 つのステップが実行されることに注意してください。1 つおきの単語ごとに 1 つ、16 ビットごとに 1 つ、1024 ビットごとに 1 つです。単語が変更された合計は、65,536 (67,108,864 の入力単語を表す) のグループに追加できます。

于 2012-01-11T00:45:26.223 に答える