algorithm - 简化 Z = X ^ (X << Y) 函数的反函数

Question

我很难将以下函数简化为几个原子二进制操作，感觉这是可能的但是我做不到，我已经挠头几个小时了:

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)这又是同样的事情，但偏移量是两倍，所以同样的技巧将再次起作用，解码更多的原始位。