選択スパン

Question

考える：

• 少なくとも一組（1）ビットを含むビットマスクa（例えば、std::uint64_t）。
• a（すなわちa & b == b）のサブセットであり、少なくとも1ビットが設定されたセレクタビットマスクb。

Iはbのビットと重複aで連続1ビットのスパンを選択する：

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

b & XXXXが偽であるため、XXXX基はcに0です。 bにはZビットの1つが設定されているため、ZZグループがコピーされます。 YYYグループも同じ理由でcに設定されています。 bは、単一グループの複数のビットをaにすることができます。 bは、これらの位置のいずれかに1を有する場合

そこでaで1 Sのすべての連続したグループのために、cにこれらのビットのすべてを設定します。より複雑な例：

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); 

私はaかつ効率的にbからcを計算することができます任意のビット論理命令/組み込み関数（MMX、SSE、AVX、BMI1/BMI2）、またはビット操作のトリックはありますか？ （ループなし）？

---

追加：

てみましょう：あなたはこのトリックを行うことuint64_tの場合

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; 

Answer 1

：私だけのループベースのアルゴリズムを想像することができデニスと答えたからヒントを使用して

a = 0b11011101101と設定します。 0ビットが少なくとも1つあることが重要です。ビットマスクには1つのビットで満たされた4つの別々の領域があります。 c=a+(a&b)を実行すると、この領域の少なくとも1ビットがbに設定されていると、1の塗りつぶし領域がそれぞれオーバーフローします。だから、あなたはどこにオーバーフローしたのかを確認することができます。あなたがaの2-ND及び3-RDエリアの1ビットをしたい場合たとえば、あなたはそうすることがあります。

assert(c & 0b00100010000); 
    //    ^^^ ^^ this segments overflows