在位掩码中选择与选择器位图中的1位重叠的设置位的跨度

Question

鉴于：

• 一种位掩码a（例如std::uint64_t），其中至少包含一组（1）位。
• 一种选择器位掩码b，它是a（a & b == b）的子集，并至少设置了一位。

我想选择连续的1位跨度，a其中与1位重叠b：

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

XXXX组为0，c因为b & XXXX为false。复制ZZ组，因为b设置了Z位之一。c出于同样的原因，也设置了YYY组。 请注意，b的单个组中可以有多个设置位a。

因此，对于1s in中的每个连续组a，将cif b中的所有这些位设置为1在这些位置中的任何位置。一个更复杂的示例：

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有效？（即没有循环）？

---

额外：

使用丹尼斯答案的提示，我只能想象基于循环的算法：

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

的情况下uint64_t你可以这样做：

让我们设定吧a = 0b11011101101。至少有一个 0 位很重要。位掩码有 4 个独立的区域，填充 1 位。如果这样做，则每个 1 填充区域将溢出（如果该区域中至少设置了c=a+(a&b)一位） 。b这样你就可以检查哪个区域被溢出了。例如，如果您希望 的第 2 个和第 3 个区域为 1 位a，则可以这样做：

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