快速查找函数f()是否具有逆函数的一个好方法是尝试找到初始域的两个元素，x并且y使得x!=y和f(x)==f(y)。

如果存在这对元素，则无法在 的目标域中区分它们f，因此无法构建反向函数。

看看你的例子：f(x) = x^(x>>11)，我们可以将结果位向量分成三部分（第一个清晰的部分来自b31to b21，第二个异或部分与第一部分（因此可以恢复）来自b20to b10，最后的第三部分可以用第二部分的明文从b9到b0) 中恢复：

x = (b31, ..., b0)

f(x) = (b31, ..., b21, b20^b31, b19^b30, ..., b10^b21, b9^b20, ..., b0^b11) 
         clear part   |      xored with clear part    | xored with previous part

所以，事实上，没有信息丢失，可以从中构建反向函数。下面是一段解释这个反向函数原理的伪代码：

g(x)
{
   /* Get the clear part */
   y = (x >> 20);

   /* Unmask the second part */
   z = ((x << 11) >> 21) ^ y;

   /* Unmask the third part */
   t = ((x << 22) >> 22) ^ z;

   /* Reassembling the whole thing */
   return (y << 20 + z << 11 + t);
  }

Perror 已经涵盖了这种特殊情况，但这里有一些用于反转相似函数的一般原则。

注意：所有这些都假设整数要么是无符号的，要么是使用二进制补码和无符号移位来签名的。在 Java 中，二进制补码是有保证的。在 C/C++ 中，不能保证，但在实践中几乎总是如此，您可以检查已编译的程序集以确保。

一系列涉及异或和位移的变换可以被认为是 (GF2)^32 中向量的线性（或仿射，如果有常数）变换。本质上，您有一个 32 元素的数字模 2 向量，并且由于 xor 是加法模 2，因此您将其乘以矩阵。

所以当矩阵可逆时，变换是可逆的。幸运的是，情况通常如此。x ^ (x >>> n)n > 0形式的函数是下三角矩阵，因此是可逆的。同样，x ^ (x << n)是一个上三角矩阵，所以也是可逆的。由于可逆矩阵的乘积是可逆的，因此任何此类变换的序列也将是可逆的。

请注意，有符号移位（Java 中的>>）不一定可逆。

至于实际反转它，最简单的方法（虽然不是最快的）是简单地计算变换矩阵条目，然后执行高斯消元（在有限域中没有舍入误差）。

您经常会看到其他操作也混合在一起。加法和乘法可以被认为是环模 2^32 中的运算。使用二进制补码，使用有符号数还是无符号数都没有关系。常数加法很简单：只需减去常数即可。乘以任何奇数常数也是可逆的：只需乘以乘法模逆。您可以在网上找到计算此值的代码，或者pow(c, (2**31)-1, 2**32)如果您正在使用 Python，则可以直接使用。

乘以偶数常数会丢失信息，因此不能完全反转。同样，具有相同效果的添加组合也不会。例如x + x是不可逆的，因为它等价于x * 2。x + (x<<4)是可逆的，因为它等价于x * 17。

由于仿射变换的组合也是仿射的，您只需将所有这些运算相乘，然后一步求逆即可节省时间。

按位 ands 和 ors 总是会丢失信息，除非在微不足道的情况下，所以它们不会可逆。但通常它们是用来以无损的方式选择部分信息进行组合，所以整体表达仍然是可逆的。例如x ^ ((x & 555) * 4)，即使表达式的两个单独组件是不可逆操作，它也是可逆的。

你可能会看到一些其他的东西。GF(2^32) 中的运算与常规加法和乘法基本相同，只是没有进位。这通常用于 CRC。加法（它只是异或）和乘以任何非零数都是可逆的，使用与以前相同的技术。

替换盒（或 sbox） - 这些被设计为可逆的，但通常没有任何特定的结构。通常，这些表示为表查找，还有一个预先计算的逆表。如果没有，假设输入不是太大，您总是可以制作自己的逆表。

我试着对你的问题给出一个非常肤浅的答案，因为我很确定这个问题还有其他的治疗方法。

在数学上，功能f(y) = y^(y >> 11)是在这个意义上，左反转，即功能可逆的g，这样y = g(f(y))存在的，因为f是一个射功能。然而，这并不意味着我们可以很容易地找到反演函数，因为它可能是不可计算的，即在这种情况下我们无法给出计算 的算法g。实际上，可能存在一些可计算的方法来“近似”它（也许是抽象解释？）。

在更严格的情况下（但可能更实用），如果 的值y存储在 4 个字节中，而 的值f(y)存储在少于 4 个字节中，那么由于鸽巢原理，该函数非常不可逆。此外，由于执行过程中信息丢失，任意指令序列的计算通常是不可逆的，我们可以考虑一个例子（在伪汇编代码中）

f(y) = 
 mov eax, y
 xor eax, eax
 return eax

thenf(y)不可逆，因为输出总是0与输入无关。然而，如果我们可以在指令的执行过程中存储一些“状态值”（即不仅是输出和指令序列），那么反转是可能的，这个想法已经在任何地方被提出，例如在GDB 反向调试或在这篇论文中。

编辑：我在这里犯了一个错误，因为我认为 ^ 是一个指数（所以我怀疑在一般情况下反转是不可计算的）但实际上它是按位排他的。

这个 python 函数适用于任何值：

def f_inv(x):
    mask= (1<<11) - 1
    a= []
    while x>0:
        a.append(x&mask)
        x >>= 11
    if not a:
       return 0
    z= a.pop()
    while a:
        z= (z<<11) | ((z&mask)^a.pop())

    return z

诀窍是将数字分成 11 位块，然后从最高的保持与前一个（更高的）块异或。和或一切在一起。