异或运算直觉

Question

我最近在 Leetcode 上遇到了 这个 问题，并想出了一个我需要澄清的解决方案：

给定一个整数数组，每个元素都出现两次，除了一个。找到那个单一的。

注意：您的算法应该具有线性运行时复杂度。你能在不使用额外内存的情况下实现它吗？

 class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int result = 0;
        for(auto & c : nums) {
            result ^= c;
        }
        return result;
    }
};

首先，我应该注意什么样的关键字才能确定我应该对这个问题使用 XOR 操作？

另外，为什么对向量中的所有项目进行异或运算会给我们一个不重复的项目？

---

谢谢大家的这些回复，这里有一些关于按位属性的更多信息，供其他感兴趣的人使用： 更多按位信息

原文由 User 5842 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

1. A ^ 0 == A

2. A ^ A == 0

3. A ^ B == B ^ A

4. (A ^ B) ^ C == A ^ (B ^ C)

(3) 和 (4) 一起表示数字 xor ed 的顺序无关紧要。

这意味着，例如， A^B^X^C^B^A^C 等于 A^A ^ B^B ^ C^C ^ X 。

因为 (2) 等于 0^0^0^X 。

因为 (1) 等于 X 。

---

我认为没有任何特定的关键字可以帮助您识别此类问题。您只需要知道 XOR 的上述属性。

原文由 HolyBlackCat 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

Xor 运算符是 可交换 的：

 1.      X ⊕ Y = Y ⊕ X                    for any integers X and Y

和 _联想_：

 2.      X ⊕ (Y ⊕ Z) = (X ⊕ Y) ⊕ Z      for any integers X, Y and Z

由此可见，任何序列 xor 运算的结果完全独立于操作数的顺序（即数组中元素的顺序）。

 3.     X ⊕ X = 0                         for any integer X

4.     X ⊕ 0 = 0 ⊕ X = X                for any integer X

---

在这个问题中，我们有一个表达式，其中每个元素 Ai 除了一些奇异元素 B 出现两次。得到的 Xor 操作等价于：

      (A1 ⊕ A1) ⊕ (A2 ⊕ A2) ⊕    ...   ⊕ B
 =
         0      ⊕      0     ⊕    ...   ⊕ B
 =
         B

---

为了弄清楚我应该对这个问题使用 XOR 操作，我应该注意哪些类型的关键字

使用位操作可以快速解决一些问题。在熟悉了布尔运算符及其属性，并且看到了足够多的此类应用程序后，您自然会“感觉到”它们对解决给定问题很有用。

原文由 A.S.H 发布，翻译遵循 CC BY-SA 3.0 许可协议