简化 Z = X ^ (X << Y) 函数的反函数
Simplify the inverse of Z = X ^ (X << Y) function
我在将以下函数简化为几个原子二进制操作时遇到了困难,感觉这是可能的但是我做不到,我已经挠头几个小时了:
public UInt32 reverse_xor_lshift(UInt32 y, Int32 shift)
{
var x = y & (UInt32)((1 << shift) - 1);
for (int i = 0; i < (32 - shift); i++) {
var bit = ((x & (1 << i)) >> i) ^ ((y & (1 << (shift + i))) >> (shift + i));
x |= (UInt32)(bit << (shift + i));
}
return x;
}
函数所做的只是计算 Z = X ^ (X << Y)
的倒数,换句话说 reverse_xor_lshift(Z, Y) == X
您可以使用与 converting back from grey code:
中使用的相同技术,用更少的操作来反转它,尽管以更难理解的方式
应用变换 z ^= z << i
,其中 i
从 shift
开始,每次迭代都加倍。
在伪代码中:
while (i < 32)
x ^= x << i
i *= 2
这是可行的,因为在第一步中,您将最低位(不受影响)异或到它们所在的位置 "xored in",因此 "xoring them out"。那么已经改成原来的部分是原来的两倍宽。新数字的形式是 x ^ (x << k) ^ (x << k) ^ (x << 2k) = x ^ (x << 2k)
,这又是同样的事情,但偏移量是原来的两倍,所以同样的技巧将再次起作用,解码更多的原始位。
我在将以下函数简化为几个原子二进制操作时遇到了困难,感觉这是可能的但是我做不到,我已经挠头几个小时了:
public UInt32 reverse_xor_lshift(UInt32 y, Int32 shift)
{
var x = y & (UInt32)((1 << shift) - 1);
for (int i = 0; i < (32 - shift); i++) {
var bit = ((x & (1 << i)) >> i) ^ ((y & (1 << (shift + i))) >> (shift + i));
x |= (UInt32)(bit << (shift + i));
}
return x;
}
函数所做的只是计算 Z = X ^ (X << Y)
的倒数,换句话说 reverse_xor_lshift(Z, Y) == X
您可以使用与 converting back from grey code:
中使用的相同技术,用更少的操作来反转它,尽管以更难理解的方式应用变换 z ^= z << i
,其中 i
从 shift
开始,每次迭代都加倍。
在伪代码中:
while (i < 32)
x ^= x << i
i *= 2
这是可行的,因为在第一步中,您将最低位(不受影响)异或到它们所在的位置 "xored in",因此 "xoring them out"。那么已经改成原来的部分是原来的两倍宽。新数字的形式是 x ^ (x << k) ^ (x << k) ^ (x << 2k) = x ^ (x << 2k)
,这又是同样的事情,但偏移量是原来的两倍,所以同样的技巧将再次起作用,解码更多的原始位。