位操作 – 掩码和聚合位

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

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

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

此操作称为 compress_right或仅压缩,并且在没有硬件支持的情况下实施起来非常糟糕.来自Hacker’s Delight“7-4 Compress,或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 = 0x80000000,则结果为x>> 31.
>如果m是2的另一个幂,则结果是(x>> numberOfTrailingZeros(m))& 1
>如果m是交替的,则可以使用“完美的非洗牌算法”.
>如果m由几个“组”组成,则可以使用“位组移动”算法(即屏蔽组,将其移位(或先移位,屏蔽第二),或将所有移位组合在一起,尽管更复杂的方法这可能是实践中最重要的案例.
> ……

例如,您问题中的掩码将落入“位组移动”的情况,代码如下：

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