XOR在算法中有哪些实际应用？

Question

老实说，我对位运算有些生疏。我感兴趣的是“异或”运算。我知道它在位运算中的作用，并且它被用于加密以及我们可以在不使用临时变量的情况下进行交换，但我想知道在算法中是否有特定的方法来应用“异或”的属性。我的意思是，我对算法中实际应用“异或”（例如，我们可以使用它来查找重复元素中的唯一元素）很感兴趣。是否有一些问题模式（或问题公式）可以看出，“异或”是解决问题的方法？（就像何时使用二分搜索一样）是否有一些与核心算法相关的实际应用“异或”的算法列表，而不仅仅是像我们可以使用“>>”代替除以2这样的数学运算来更快地执行操作。 欢迎任何意见。

- Cratylus

---

好的，其他哈希算法（包括非加密算法）都会在某个地方使用异或运算符。这样算数吗，还是仍然只是“位操作”？ - user395760

我希望能找到解决问题的最佳方法。例如，当您尝试在重复项中查找唯一项时，可以使用哈希表，但是也可以使用“XOR”而无需额外的空间，因为重复项会被取消。 - Cratylus

网络上最重要的问题之一，它已经关闭了... - Royi Namir

Answer 1

几个我想到的例子：

切换位：

int i = 123;
i ^= (1 << 4); // toggle bit 5

一些随机性：

int i = 123;
for (int k = 0; k < 100; k++)
{
   i = i ^ (i << 1) + i;
   System.out.println(i);
}

"弱加密"

int b = 235321;
int key = 24552;
int encrypted = b ^ key;
int decrypted = encrypted ^ key; // equals 235321

- Martijn Courteaux

---

这正是我写“weak”的原因。 - Martijn Courteaux

顺便说一下，最后一个可以扩展到轻松加密纯文本（您只需一个编码）。如果密钥是随机的并且与输入一样长，那么它实际上是一个相当好的密码，因为无法破解（既不知道密钥也不知道明文）。如果密钥较短（因此重复以适应输入的长度），则可以轻松地破解它（对专家来说很容易），但唯一剩下的问题是创建一次性密码并将其发送给Bob。密码学很迷人。 - user395760