5

鉴于：

  • 一个位掩码a（比如std::uint64_t），它至少包含一个 set ( 1) 位。
  • 选择器位掩码b，它是a(ie a & b == b) 的子集，并且具有至少一个位集。

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

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

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

1因此，对于s 中的每个连续组a，将所有这些位设置为cif在任何这些位置中b有 a 。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地 进行计算？（即没有循环）？ab

额外的：

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

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

1 回答 1

4

如果uint64_t你可以这样做：

让我们设置a = 0b11011101101。至少有一个 0 位很重要。位掩码有 4 个单独的区域，用 1 位填充。如果你这样做了，那么如果在该区域中设置c=a+(a&b)了至少一位，则每个填充为 1 的区域都会溢出。b所以你可以检查，哪个区域被溢出了。例如，如果您想在 的 2-nd 和 3-rd 区域中使用 1 位a，您可以这样做：

    assert(c & 0b00100010000);
    //              ^^^ ^^ this segments overflows
于 2016-05-19T04:55:55.890 回答