3

サイズが N 文字のビットマスクがあり、これは静的にわかっています (つまり、コンパイル時に計算できますが、単一の定数ではないため、書き留めることはできません)。 「欲しい」ビット。そして、同じサイズの値がありますが、これは実行時にのみわかります。その値から「必要な」ビットを順番に新しい値の先頭に集めたいと思います。簡単にするために、必要なビット数が <= 32 であると仮定しましょう。

うまくいけば正しい動作をする、完全に最適化されていない参照コード:

template<int N, const char mask[N]>
unsigned gather_bits(const char* val)
{
    unsigned result   = 0;
    char*    result_p = (char*)&result;
    int      pos      = 0;
    for (int i = 0; i < N * CHAR_BIT; i++)
    {
        if (mask[i/CHAR_BIT] & (1 << (i % CHAR_BIT)))
        {
            if (val[i/CHAR_BIT] & (1 << (i % CHAR_BIT)))
            {
                if (pos < sizeof(unsigned) * CHAR_BIT)
                {
                    result_p[pos/CHAR_BIT] |= 1 << (pos % CHAR_BIT);
                } 
                else
                {
                    abort();
                }
            }
            pos += 1;
        }
    }
    return result;
}

その定式化が実際にコンパイル時にマスクの内容へのアクセスを許可するかどうかはわかりませんが。しかし、いずれにせよ、それは使用可能です。おそらく、constexpr関数または何かがより良いアイデアになるでしょう. 私はここで必要な C++ の魔法を探しているわけではありません (それは後で調べます)、アルゴリズムだけです。

わかりやすくするために、16 ビット値と虚数バイナリ表記を使用した入力/出力の例:

mask   = 0b0011011100100110
val    = 0b0101000101110011
--
wanted = 0b__01_001__1__01_ // retain only those bits which are set in the mask
result = 0b0000000001001101 // bring them to the front
                   ^ gathered bits begin here

私の質問は次のとおりです。

  • これを行う最もパフォーマンスの高い方法は何ですか? (役立つハードウェアの説明はありますか?)

  • マスクと値の両方が に制限されている場合はどうなるでしょうか?つまりunsigned、無制限の char 配列ではなく、1 つの単語でしょうか? それでは、固定された短い一連の命令でそれを行うことができますか?

4

1 に答える 1

4

Intel Haswellで必要なことを正確に行うpext（パラレルビット抽出）があります。その命令のパフォーマンスがどうなるかはわかりませんが、おそらく代替手段よりも優れています。この操作は、「compress-right」または単に「compress」とも呼ばれます。Hacker's Delight の実装は次のとおりです。

unsigned compress(unsigned x, unsigned m) {
   unsigned mk, mp, mv, t; 
   int i; 

   x = x & m;           // Clear irrelevant bits. 
   mk = ~m << 1;        // We will count 0's to right. 

   for (i = 0; i < 5; i++) {
      mp = mk ^ (mk << 1);             // Parallel prefix. 
      mp = mp ^ (mp << 2); 
      mp = mp ^ (mp << 4); 
      mp = mp ^ (mp << 8); 
      mp = mp ^ (mp << 16); 
      mv = mp & m;                     // Bits to move. 
      m = m ^ mv | (mv >> (1 << i));   // Compress m. 
      t = x & mv; 
      x = x ^ t | (t >> (1 << i));     // Compress x. 
      mk = mk & ~mp; 
   } 
   return x; 
}
于 2013-01-07T18:37:11.747 に答える