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

Question

给定：

位掩码 a（例如，std::uint64_t），其中至少包含一组 (1) 位。
A select 或位掩码 b 是 a 的子集（即 a & b == b），并且至少设置了一位。

我想 select a 中的连续 1 位跨度与 b 中的位重叠：

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

XXXX组在c中为0，因为b & XXXX为假。 ZZ 组被复制，因为 b 设置了 Z 位之一。 YYY组也是在c中设置的，同理。 请注意 b 可以在 a.

的单个组中设置多个位

因此，对于 a 中每个连续的 1 组，如果 b 在任何那些职位。一个更复杂的例子：

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

是否有任何位逻辑 instructions/intrinsics（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

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

Select spans of set bits in a bitmask that overlap with a 1-bit in a selector bitmap

c++

x86

bit-manipulation

bmi