有趣的 XOR 技巧

Table of Contents

XOR（异或位运算）自反性：

  • 任何数异或自己得到 0
  • 任何数疑惑异或 0 等于本身

利用这个特性可以快速解决力扣题 136. 只出现一次的数字。

题目复述

给定一个非空数组，除了某个元素出现一次外，其他元素均出现两次。找出那个只出现一次的元素值。

当然可以模拟

创建键为元素值、值为其在数组出现次数的哈希表；遍历数组，记录每个元素出现的次数，最终值为 1 的键就是需要找的元素。

不过题目要求只能使用额外常量空间，所以不能用该方法。

利用 XOR 更巧妙

题目已知出目标元素之外的都会出现两次，这些值异或为 0 （0 ^ 0 == 0）。也就是说，将数组的全部元素使用异或运算，最终的结果就是要找的结果元素。

代码

int singleNumber(vector<int>& nums) {
    int ret = 0;
    for (auto e : nums) ret ^= e;
    return ret;
}