简化Z = X ^的倒数（X＆LT;＆LT; Y）功能 [英] Simplify the inverse of Z = X ^ (X << Y) function

问题描述

我有困难简化了以下功能分为几个几个原子二进制运算，感觉这是可能的但我无法做到这一点，我抓我的头几个小时了：

I'm having difficulty with simplifying the following function into several several atomic binary operations, it feels like it's possible however I'm unable to do it, I'm scratching my head for few hours already:

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＆LT;＆LT; Y），换句话说 reverse_xor_lshift（Z，Y）= = X

推荐答案

您可以用少得多的操作逆它，尽管更难理解的方式，用同样的方法在的从灰色code 转换回：

You can inverse it with much fewer operations, though in a harder to understand way, by using the same technique as used in converting back from grey code:

应用转换 Z 2 = z，其中;＆LT;我，其中我开始于移和双打每个迭代。

Apply the transformation z ^= z << i where i starts at shift and doubles every iteration.

在伪code：

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

这工作，因为在第一个步骤中，异或最低位（不受影响）通过他们在那里或运算中的地方，因而异或出来。然后已被变更为原来的部分是两倍宽。新的数字是形式 X ^那么（X＆LT;＆LT; K）^（X＆LT;＆LT; K）^（X＆LT;＆LT; 2K）= X ^（X＆LT;＆LT ;。2K）这是同样的事情再次但是偏移的两倍，所以同样的伎俩会重新工作，解码了更多的原始比特

This works because in the first step, you xor the lowest bits (unaffected) by the place where they were "xored in", thus "xoring them out". Then the part that has been changed to the original is twice as wide. The new number is then of the form x ^ (x << k) ^ (x << k) ^ (x << 2k) = x ^ (x << 2k) which is the same thing again but with twice the offset, so the same trick will work again, decoding yet more of the original bits.

这篇关于简化Z = X ^的倒数（X＆LT;＆LT; Y）功能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！