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

Question

给定:

• 一个位掩码 a(例如，std::uint64_t)，其中至少包含一组 (1) 位。
• 选择器位掩码 b 是 a 的子集(即 a & b == b)，并且至少有一位设置。

我想在 a 中选择与 b 中的位重叠的连续 1 位的跨度:

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

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

因此对于 a 中每个连续的 1 组，如果 b，则将所有这些位设置在 c 中> 在任何这些位置都有一个 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)或位操作技巧允许我从a计算c和 b 有效吗？ (即没有循环)？

---

附加:

使用 Denis 的回答中的提示，我只能想象基于循环的算法:

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 个位。如果您执行c=a+(a&b)，那么如果该区域中的至少一位b 被设置，则每个1 填充区域将溢出。这样您就可以检查哪个区域被溢出了。例如，如果您想要在 a 的第 2 和第 3 区域中使用 1 位，您可以这样做:

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