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

Question

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

7

我正在尝试将以下函数简化为几个原子二进制操作，虽然感觉可能性很大，但我却做不到。已经想了好几个小时了:

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。

- Lu4

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- harold · Accepted Answer

您可以使用与从格雷码转换回来相同的技术，以更难理解的方式，通过更少的操作来反转它:

应用变换z ^= z << i，其中i从shift开始，每次迭代加倍。

伪代码如下:

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

这个方法可行是因为在第一步中，将最低位（未受影响）与其“异或”位置相异或，从而“抵消”它们。然后被改变回原始值的部分变成了两倍宽。新数字的形式为 x ^ (x << k) ^ (x << k) ^ (x << 2k) = x ^ (x << 2k)，再次使用相同的技巧，但偏移量增加了两倍，因此同样的技巧可以解码更多原始位。