扩展右按位算法 [英] Expand Right Bitwise Algorithm
问题描述
最初,该帖子要求进行逆山羊和山羊操作,但是我意识到这远远超出了我的实际需要,所以我编辑了标题,因为我只需要一个
Originally this post requested an inverse sheep-and-goats operation, but I realized that it was more than I really needed, so I edited the title, because I only need an expand-right algorithm, which is simpler. The example that I described below is still relevant.
原始帖子:
我正在尝试找出如何进行逆向山羊和山羊的操作,或者甚至更好地执行右向翻转的操作.
I'm trying to figure out how to do either an inverse sheep-and-goats operation or, even better, an expand-right-flip.
根据 Hacker's Delight ,绵羊和山羊的行动可以用以下方式表示:
According to Hacker's Delight, a sheeps-and-goats operation can be represented by:
SAG(x, m) = compress_left(x, m) | compress(x, ~m)
根据此站点,可以通过以下方式找到反函数:
According to this site, the inverse can be found by:
INV_SAG(x, m, sw) = expand_left(x, ~m, sw) | expand_right(x, m, sw)
但是,我找不到关于expand_left和expand_right函数的任何代码.当然,它们是compress的逆函数,但是compress本身很难理解.
However, I can't find any code for the expand_left and expand_right functions. They are, of course, the inverse functions for compress, but compress is kind of hard to understand in itself.
示例:
为了更好地解释我在寻找什么,请考虑一组8位,例如:
To better explain what I'm looking for, consider a set of 8 bits like:
0000abcd
变量a,b,c和d可以为1或0.此外,还有一个掩码,用于重新定位位.因此,例如,如果掩码为01100101
,则结果位将按以下方式重新定位:
The variables a, b, c and d may be either ones or zeros. In addition, there is a mask which repositions the bits. So for example, if the mask were 01100101
, the resulting bits would be repositioned as follows:
0ab00c0d
这可以通过逆山羊和山羊操作来完成.但是,根据上述网站的本节,有一种更有效的方法他称为右上翻.在他的网站上,我无法弄清楚该怎么做.
This can be done with an inverse sheeps-and-goats operation. However, according to this section of the site mentioned above, there is a more efficient way which he refers to as the expand-right-flip. Looking at his site, I was unable to figure out how that can be done.
推荐答案
这是Hacker's Delight的expand_right
,只说了expand
,但它是right
版本.
Here's the expand_right
from Hacker's Delight, it just says expand
but it's the right
version.
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
版本,但这可能不是最好的方法.
You can use expand_left(x, m) == expand_right(x >> (32 - popcnt(m)), m)
to make the left
version, but that's probably not the best way.
这篇关于扩展右按位算法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!