按位右展开算法

本来这篇文章要求逆绵羊和山羊操作，但我意识到这超出了我的实际需要，所以我编辑了标题，因为我只需要一个右展开算法 http://programming.sirrida.de/bit_perm.html#c_e，这更简单。我在下面描述的示例仍然具有相关性。

原帖：

我正在尝试弄清楚如何进行反向绵羊和山羊操作，或者更好的是展开右翻转。

根据黑客的喜悦 http://hackersdelight.org/，绵羊和山羊操作可以表示为：

SAG(x, m) = compress_left(x, m) | compress(x, ~m)

根据这个网站 http://programming.sirrida.de/bit_perm.html#sag，逆矩阵可以通过以下方式找到：

INV_SAG(x, m, sw) = expand_left(x, ~m, sw) | expand_right(x, m, sw)

但是，我找不到 Expand_left 和 Expand_right 函数的任何代码。当然，它们是 compress 的反函数，但 compress 本身有点难以理解。

Example:

为了更好地解释我正在寻找的内容，请考虑一组 8 位，例如：

0000abcd

变量a、b、c和d可以是1或0。此外，还有一个可以重新定位位的掩码。例如，如果面具是01100101，结果位将被重新定位如下：

0ab00c0d

这可以通过逆绵羊和山羊操作来完成。然而，根据本节 http://programming.sirrida.de/bit_perm.html#c_e_flip对于上述站点，有一种更有效的方法，他称之为展开右翻转。看着他的网站，我无法弄清楚如何做到这一点。

这是expand_right来自黑客之乐，它只是说expand但这是right版本。

unsigned expand(unsigned x, unsigned m) {
    unsigned m0, mk, mp, mv, t;
    unsigned array[5];
    int i;
    m0 = m;        // Save original mask.
    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.
        array[i] = mv;
        m = (m ^ mv) | (mv >> (1 << i)); // Compress m.
        mk = mk & ~mp;
    }
    for (i = 4; i >= 0; i--) {
        mv = array[i];
        t = x << (1 << i);
        x = (x & ~mv) | (t & mv);
    }
    return x & m0;     // Clear out extraneous bits.
}

您可以使用expand_left(x, m) == expand_right(x >> (32 - popcnt(m)), m)使left版本，但这可能不是最好的方法。