5

与えられた:

  • 少なくとも 1 つのセット ( ) ビットを含むビットマスクa(たとえば、 )。std::uint64_t1
  • (つまり)bのサブセットであり、少なくとも 1 つのビット セットを持つセレクター ビットマスク。aa & b == b

aのビットと重複する連続した 1 ビットのスパンを選択したいb:

a = 0b1111001110001100;
b = 0b0000001010001000;
//c=0b0000001110001100
//    XXXX  YYY   ZZ

が falseでcあるため、XXXX グループは 0です。Z ビットの 1 つが設定されているb & XXXXため、ZZ グループがコピーされます。同じ理由 bで YYY グループも設定されています。では、1 つのグループに複数のビットを設定できることに注意してください。cba

1したがって、 内のs の連続するグループごとに、これらの位置のいずれかにがある場合は、内aのすべてのビットを設定します。より複雑な例:cb1

std::uint64_t a = 0b1101110110101;
std::uint64_t b = 0b0001010010001;
// desired   c == 0b0001110110001
// contiguous groups   ^^^ ^^   ^  that overlap with a 1 in b

assert(a & b == b);           // b is a subset of a

std::uint64_t c = some_magic_operation(a, b);
assert(c == 0b0001110110001);

ビット論理命令/組み込み関数 (MMX、SSE、AVX、BMI1/BMI2)、または効率的に計算できるビット操作のトリックはありcます aかb? (つまり、ループなし)?

追加：

Denis' answer からのヒントを使用すると、ループベースのアルゴリズムしか想像できません。

std::uint64_t a = 0b0110111001001101;
std::uint64_t b = 0b0100101000001101;
assert(a & b == b); // subset

std::cout << std::bitset< 16 >(a) << std::endl;
std::cout << std::bitset< 16 >(b) << std::endl;
std::uint64_t x = (a + b) & ~a;
std::uint64_t c = 0;
while ((x = (a & (x >> 1)))) { // length of longest 1-series times
    c |= x;
}
std::cout << std::bitset< 16 >(c) << std::endl;
4

1 に答える 1