简化Z = X ^（X << Y）函数的逆函数

Question

我很难将以下函数简化为几个原子二进制运算，但感觉像是可能的，但是我无法做到这一点， “M抓我的头几个小时了：

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

Answer 1

你可以用少得多的操作逆它，但在通过使用与在converting back from grey code中使用的相同的技术更难以理解的方式：

应用转换z ^= z << i其中i从shift开始并且每次迭代都加倍。

伪代码：

while (i < 32) 
    x ^= x << i 
    i *= 2 

这工作，因为在第一个步骤中，您异或最低位（影响），通过他们在那里“在异或运算”的地方，因此，“异或出来”。然后，更改为原件的部分宽度是其两倍。新号码的格式为x^(x << k)^(x << k)^(x << 2k) = x^(x << 2k)，它又是一样的东西，但是具有两倍的偏移量，所以同样的技巧将再次起作用，解码更多的原始比特。