最初这篇文章要求一个逆向的绵羊和山羊操作,但我意识到这比我真正需要的要多,所以我编辑了标题,因为我只需要一个expand-right algorithm。 ,这更简单。我在下面描述的示例仍然适用。
原帖:
我正在尝试弄清楚如何执行反向绵羊和山羊操作,或者更好的是,展开右翻转。
根据 Hacker's Delight ,绵羊和山羊的操作可以表示为:
SAG(x, m) = compress_left(x, m) | compress(x, ~m)
根据 this site ,可以通过以下方式找到逆:
INV_SAG(x, m, sw) = expand_left(x, ~m, sw) | expand_right(x, m, sw)
但是,我找不到 expand_left 和 expand_right 函数的任何代码。当然,它们是压缩的反函数,但压缩本身有点难以理解。
示例:
为了更好地解释我在寻找什么,请考虑一组 8 位,例如:
0000abcd
变量 a、b、c 和 d 可以是 1 也可以是 0。此外,还有一个重新定位位的掩码。因此,例如,如果掩码是 01100101
,则结果位将按如下方式重新定位:
0ab00c0d
这可以通过反向绵羊和山羊操作来完成。然而,根据this section在上面提到的站点中,有一种更有效的方法,他称之为 expand-right-flip。查看他的网站,我无法弄清楚如何做到这一点。
最佳答案
这是来自 Hacker's Delight 的 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
版本,但这可能不是最好的方法。
关于algorithm - 向右展开按位算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16568134/