cd ../archive

异或

#算法#异或

运算规则

异或运算有一些重要的性质：

  • 任何数和 0 做异或运算，结果仍然是原来的数。a⊕0=aa \oplus 0 = a
  • 任何数和其自身做异或运算，结果是 0。a⊕a=0a \oplus a = 0
  • 异或运算满足交换律和结合律。a⊕b⊕a=a⊕a⊕b=0⊕b=ba \oplus b \oplus a = a \oplus a \oplus b = 0 \oplus b = b

例子

只出现一次的数字

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间

考虑异或运算

相同的数字（即出现两次的数字）进行异或位运算后为0。因此，可以设 aa 为 0，然后扫描整个数组，让 aa 和数组所有数进行异或运算，最后得到的结果就是只出现一次的数。