8

Intel の Bit Manipulation Instruction Set 2 (BMI2)のパラレル デポジット命令( )のドキュメントでは、次の命令のシリアル実装について説明しています (C に似た擬似コード)。PDEP

U64 _pdep_u64(U64 val, U64 mask) {
  U64 res = 0;
  for (U64 bb = 1; mask; bb += bb) {
    if (val & bb)
      res |= mask & -mask;
    mask &= mask - 1;
  }
  return res;
}

Intel のpdepinsn ref マニュアル エントリも参照してください。

このアルゴリズムは O(n) です。ここで、n は のセット ビット数ですmask。これは明らかに O(k) の最悪のケースを持ちます。ここで、k は の総ビット数ですmask。

より効率的な最悪のケースのアルゴリズムは可能ですか?

val最大で 1 つのビットが設定されている、つまり 0 に等しいか、0 から 63 まで1<<rの値に等しいと仮定する、より高速なバージョンを作成することは可能ですか?r

4

1 に答える 1

4

質問の 2 番目の部分である 1 ビット デポジットの特殊なケースについては、2 つの手順が必要です。r最初のステップでは、 の単一の 1ビットvalのビット インデックスを決定する必要がvalあります。これは、POSIX function を介して簡単に実現できますffs。または、r他の手段でわかっている場合は、コメントで質問者が示唆しているように。2 番目のステップでは、存在する場合i、 のr番目の 1ビットのビット インデックスを特定する必要があります。次に、 at bitの- 番目のビットをmaskデポジットできます。rvali

r- 番目の 1 ビットのインデックスを見つける 1 つの方法は、2 分割に基づく従来の人口カウントmaskアルゴリズムを使用して 1 ビットを集計し、中間のグループ単位のビット カウントをすべて記録することです。次に、記録されたビット カウント データに対してバイナリ検索を実行して、目的のビットの位置を特定します。

次のCコードは、64 ビット データを使用してこれを示しています。maskこれが実際に反復法より速いかどうかは、との典型的な値に大きく依存しますval。

#include <stdint.h>

/* Find the index of the n-th 1-bit in mask, n >= 0
   The index of the least significant bit is 0 
   Return -1 if there is no such bit
*/
int find_nth_set_bit (uint64_t mask, int n)
{
    int t, i = n, r = 0;
    const uint64_t m1 = 0x5555555555555555ULL; // even bits
    const uint64_t m2 = 0x3333333333333333ULL; // even 2-bit groups
    const uint64_t m4 = 0x0f0f0f0f0f0f0f0fULL; // even nibbles
    const uint64_t m8 = 0x00ff00ff00ff00ffULL; // even bytes
    uint64_t c1 = mask;
    uint64_t c2 = c1 - ((c1 >> 1) & m1);
    uint64_t c4 = ((c2 >> 2) & m2) + (c2 & m2);
    uint64_t c8 = ((c4 >> 4) + c4) & m4;
    uint64_t c16 = ((c8 >> 8) + c8) & m8;
    uint64_t c32 = (c16 >> 16) + c16;
    int c64 = (int)(((c32 >> 32) + c32) & 0x7f);
    t = (c32    ) & 0x3f; if (i >= t) { r += 32; i -= t; }
    t = (c16>> r) & 0x1f; if (i >= t) { r += 16; i -= t; }
    t = (c8 >> r) & 0x0f; if (i >= t) { r +=  8; i -= t; }
    t = (c4 >> r) & 0x07; if (i >= t) { r +=  4; i -= t; }
    t = (c2 >> r) & 0x03; if (i >= t) { r +=  2; i -= t; }
    t = (c1 >> r) & 0x01; if (i >= t) { r +=  1;         }
    if (n >= c64) r = -1;
    return r; 
}

/* val is either zero or has a single 1-bit.
   Return -1 if val is zero, otherwise the index of the 1-bit
   The index of the least significant bit is 0
*/
int find_bit_index (uint64_t val)
{
    return ffsll (val) - 1;
}

uint64_t deposit_single_bit (uint64_t val, uint64_t mask)
{
    uint64_t res = (uint64_t)0;
    int r = find_bit_index (val);
    if (r >= 0) {
        int i = find_nth_set_bit (mask, r);
        if (i >= 0) res = (uint64_t)1 << i;
    } 
    return res;
}
于 2016-08-14T19:34:42.243 に答える