bit-manipulation - 掩码和聚合位

Question

我正在尝试有效地执行以下任务:

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

我希望这个例子能清楚地解释我想要实现的目标。以非天真的方式做到这一点的最佳方法是什么？

Answer 1

此操作称为 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);

(这也在 Hacker's Delight 中，格式略有不同)

许多情况可以再次更简单，例如:

如果 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是交替的，可以使用“完美的unshuffle算法”。

如果 m由几个“组”组成，可以使用“位组移动”算法(即屏蔽一个组，将其移动到位(或先移动，第二个屏蔽)，或将所有移动的组放在一起，尽管存在更复杂的方法)，这可能是实践中最重要的案例。

...

例如，您问题中的掩码将属于“位组移动”情况，代码如下:

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