掩码和聚合位

Question

掩码和聚合位

5

我将尝试高效地执行下列任务：

INPUT VALUE: 01101011
MASK:        00110010
MASK RESULT: --10--1-
AGGREGATED:  00000101

我希望这个例子能清楚地解释我想要实现的内容。在不太幼稚的方式下，最好的方法是什么？

- Filippo Bistaffa

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- harold · Accepted Answer

这个操作被称为compress_right或者简单地叫做compress，如果没有硬件支持，实现起来会比较困难。Hacker's Delight中的非朴素代码“7-4 Compress, or Generalized Extract”用于实现此函数：

unsigned compress(unsigned x, unsigned m) {
    unsigned mk, mp, mv, t;
    int i;
    x = x & m;    // Clear irrelevant bits.
    mk = ~m << 1; // We will count 0's to right.
    for (i = 0; i < 5; i++) {
        mp = mk ^ (mk << 1);    // Parallel suffix.
        mp = mp ^ (mp << 2);
        mp = mp ^ (mp << 4);
        mp = mp ^ (mp << 8);
        mp = mp ^ (mp << 16);
        mv = mp & m;     // Bits to move.
        m = m ^ mv | (mv >> (1 << i)); // Compress m.
        t = x & mv;
        x = x ^ t | (t >> (1 << i));   // Compress x.
        mk = mk & ~mp;
    }
    return x;
}

BMI2 (实现在 Haswell 和更高版本) 将拥有指令 pext 用于此操作。

如果掩码是一个常量 (或者不是一个常量但被多次重复使用)，一个相对显而易见的优化是预先计算循环期间 mv 取得的 5 个值。计算 mv 不依赖于 x，因此可以像下面这样独立计算 (与上述算法相同)。

mk = ~m << 1;
for (i = 0; i < 5; i++) {
    mp = mk ^ (mk << 1);
    mp = mp ^ (mp << 2);
    mp = mp ^ (mp << 4);
    mp = mp ^ (mp << 8);
    mp = mp ^ (mp << 16);
    mv = mp & m;
    mask[i] = mv;
    m = m ^ mv | (mv >> (1 << i));
    mk = mk & ~mp;
}

仍然看起来复杂，但这里的所有内容都是常量，因此可以进行预计算（如果编译器无法完成，则您可以通过运行它并将结果粘贴到代码中来完成）。代码的“实际部分”，也就是必须在运行时实际执行的代码如下：

x = x & m;
t = x & mask[0];
x = x ^ t | (t >> 1);
t = x & mask[1];
x = x ^ t | (t >> 2);
t = x & mask[2];
x = x ^ t | (t >> 4);
t = x & mask[3];
x = x ^ t | (t >> 8);
t = x & mask[4];
x = x ^ t | (t >> 16);

（这也在《黑客的惊喜》中，格式略有不同）

许多情况可能会更简单，例如：

如果 m = 0，结果为 0。

如果 m = -1，结果为 x。

如果 m = 1，结果为 x & 1。

如果 m = ((1 << n) - 1) << k，结果为 (x >> k) & m。

如果 m = 0x80000000，结果为 x >> 31。

如果 m 是其他的2的幂次方，结果为 (x >> numberOfTrailingZeros(m)) & 1。

如果 m 是交替的，可以使用“完美的去混洗算法”。

如果 m 由几个“组”组成，则可以使用“位组移动”算法（即掩码一组，将其移入位（或先移位，后掩码），将所有移位的组进行OR运算在一起，尽管存在更复杂的方法），这可能是实际中最重要的情况之一。

例如，在您的问题中提到的掩码将落在“位组移动”情况中，使用以下代码：

return ((x >> 1) & 1) | ((x >> 3) & 6);