Select Spannweiten der gesetzten Bits in einer Bitmaske, die mit einem 1-Bit in einem Selektor Bitmap überlappen

Question

Gegeben:

• A Bitmaske a (sagen wir, std::uint64_t), die mindestens einen Satz (1) Bit enthält. Eine Selektor-Bitmaske b, die eine Teilmenge von a ist (d.

Ich möchte a Spannweiten von zusammenhängenden 1-Bits wählen, die in b mit einem Bit überlappen:

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

Die XXXX Gruppe 0 in c weil b & XXXX falsch ist. Die ZZ-Gruppe wird kopiert, weil b eines der Z-Bits gesetzt hat. Die YYY-Gruppe wird aus dem gleichen Grund auch in c eingestellt. Beachten Sie, dass b mehrere Set-Bits in einer einzelnen Gruppe in a haben kann.

So wird für jede zusammenhängende Gruppe von 1 s in a, setzen alle diese Bits in c wenn b ein 1 in jedem dieser Positionen hat. Ein komplexeres Beispiel:

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

Gibt es irgendwelche Bit-Logikanweisungen/intrinsics (MMX, SSE, AVX, BMI1/BMI2) oder Bit-Manipulations Tricks, die mir c von a und b effizient berechnen können? (d. h. ohne Schleifen)?

---

ZUSÄTZLICH:

Mit Hinweis von Denis' Antwort, die ich nur Loop-basierte Algorithmus vorstellen kann:

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

Bei uint64_t Sie diesen Trick tun kann:

Lassen Sie uns Set a = 0b11011101101. Es ist wichtig, mindestens ein 0 Bit zu haben. Die Bitmaske hat 4 getrennte Bereiche, die mit 1 Bit gefüllt sind. Wenn Sie c=a+(a&b) machen, wird jeder 1-gefüllte Bereich überlaufen, wenn mindestens ein Bit von b in diesem Bereich gesetzt ist. Sie können also prüfen, welcher Bereich überflogen wurde. Zum Beispiel, wenn Sie 1-Bits in 2-nd und 3-rd Bereichen a möchten, können Sie dies tun:

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