异或运算的巧用|异或运算的巧用 → 不用额外的变量，如何交换两个变量的值（）
开心一刻
两头奶牛在一起吃草，其中一头（奶牛甲）越吃越慢，一副若有所思的模样，另一头奶牛（奶牛乙）发觉了，开始了对话
奶牛乙：搁那合计啥呢？
奶牛甲：你帮我合计合计
奶牛乙：咋地了
奶牛甲：我吃的是草，挤出来的是奶，也就是说我把没用的变成有用的了
奶牛乙：是这个事
奶牛甲：人呢，喝的是奶，拉出来的是粑粑
奶牛乙：咋地了
奶牛甲：他又把有用的变成没用的了，我这不白干了吗
奶牛乙：你说的不对
奶牛甲：不对吗？
奶牛乙：那粑粑做成化肥，有化肥才能长草，所以说你吃的不是草，是粑粑
奶牛乙：啊 ？？？
文章图片
概念
关于“位”运算，大家或多或少都知道点，比如与运算（&）、或运算（|）、异或运算（^）、取反运算（~）、左移（<<）、右移（>>）
因为今天的主角是：异或运算，其他的位运算就不在本文展开了，大家自行去查阅
异或运算的英文名： exclusive OR ，简称 XOR ，那它是不是和或运算有什么关系？
关于或运算，我们都比较清楚，只有当两个位都是0时，结果才为0，其他情况结果都是1，也就是说或运算结果为 1 的情况两种
（1）一个位是 1，另一个位是 0
（2）两个位都是 1
有时候我们需要明确区分这两种情况，怎么办？
所以引入了 XOR ，它排除了情况（2），只有情况（1），也就说：一个位是 1，另一个位是 0 时， XOR 的结果才是 1，因此也可称做无进位相加
所以XOR 可以看成是更单纯的 OR 运算，正好对应了它的英文名： exclusive OR ，用来判断两个值是否不同（不同、不同、不同！！！）
XOR 的运算真值表
文章图片
运算定律
我们学过的加法、乘法都有运算定律，异或运算也有它的运算定律
N ^ N = 0
N 表示任何值，也就是说：两个相等的值做异或运算，得到的结果是 0
【异或运算的巧用|异或运算的巧用 → 不用额外的变量，如何交换两个变量的值（）】因为值相等，那么值对应的各个位的值也是相等的，对应到 XOR 的运算真值表则是
文章图片
我们来看个具体的例子：15 ^ 15
15 对应的二进制位： 01111 ，那么 15 ^ 15 的运算则是
文章图片
N ^ 0 = 0
一个值与 0 做异或运算，得到的结果仍是这个值
例如：15 ^ 0 = 15
文章图片
N ^ M = M ^ N
同加法有交换律、乘法也有交换律一样，异或运算也有交换律
例如：15 ^ 8 = 8 ^ 15
文章图片
(N ^ M) ^ Y = N ^ (M ^ Y)
同加法有结合律、乘法有结合律一样，异或运算也结合律
例如：(15 ^ 8) ^ 3 = 15 ^ (8 ^ 3)
文章图片
具体应用
前面讲了那么多理论，大家可能没啥感觉，接下来我们就看看具体的案例，让大家好好感觉感觉
不用额外的变量，交换两个变量的值
楼主在以往的面试过程中，确确实实被面到过这个问题，关键是当时没答上来
这个问题的考点就是 XOR
假设这两个变量分别是 N（值为 5）、M（值为 6），通过三次 XOR 即可交换 N、M 的值
N = N ^ M// N = 5 ^ 6， M = 6
M = N ^ M// M = 5 ^ 6 ^ 6 = 5 ^ 0 = 5，N = 5 ^ 6
N = N ^ M// N = 5 ^ 6 ^ 5 = 6 ^ 0 = 6，M = 5
文章图片
找出一串数字中唯一出现了奇数次的数字
问题详细描述：已知一串数中，只有 1 个数字出现了奇数次，其他数字都出现了偶数次，如何快速找到这个奇数次的数字
如果没有任何限制，解决方式有很多种，而最容易想到的往往是用 哈希表
对这串数字从头遍历到尾， 逐个判断该数字是否存在于哈希表 ，没有存在则存入 哈希表 ，存在了则从 哈希表 中移除
最终 哈希表 中剩下的那个数字就是出现了奇数次的数字
哈希表 方案的时间复杂度是 O(N) ，额外空间复杂度也是 O(N)
假设加个限制：额外空间复杂度 O(1)
这时候就该 XOR 出马了，我们结合 N ^ N = 0 、异或的交换律、异或的结合律，可推算出：这串数字全部进行异或运算，最终的结果就是出现了奇数次的那个数字
文章图片
此时的额外空间复杂度是 O(1) ，只用到了两个额外变量： eor 、 cur
找出 1 至 n 中缺少的那个数
问题详细描述：一串数字包含 n-1 个成员，这些数字是 1 到 n 之间的整数，且没有重复，请找出缺少的那个数字
常规解法：从 1 累和到 n，然后再逐个减去这串数字
类似这样 1 + 2 + ... + n - arr[0] - arr[1] - ... - arr[n-2]
文章图片
时间复杂度 O(N) ，空间复杂度 O(1) ，似乎很完美
但是求和的过程存在溢出的风险，那怎么办？ XOR 闪亮登场
我们将这串数组与 1 至 n 的每个整数放在一起进行全部的异或运算
类似这样 arr[0] ^ arr[1] ^ ... ^ arr[n-2] ^ 1 ^ 2 ^ ... ^ n
文章图片
那么得到的结果就是缺少的那个数
不存在溢出的风险，并且位运算比加、减运算更快
找出 1 至 n 中重复的那个数字
问题详细描述：一串数字包含 n+1 个成员，这些数字是 1 到 n 之间的整数，只有一个数字出现了两次，其他数字都只出现一次，请找出重复出现的那个数字
与问题：找出 1 至 n 中缺少的那个数解法一致
arr[0] ^ arr[1] ^ ... ^ arr[n] ^ 1 ^ 2 ^ ... ^ n
文章图片
找出一串数字中出现了奇数次的那两个数字
问题详细描述：已知一串数中，有 2 个数字出现了奇数次，其他数字都出现了偶数次，如何快速找到那 2 个奇数次的数字
要求：时间复杂度 O(N) ，空间复杂度 O(1)
经过上面几题的洗礼，我相信大家对 奇数次 、 偶数次 字眼已经产生了条件反射：用 XOR
我们对这串数字进行 XOR ，那么得到的结果 eor = a ^ b ，a 和 b 就是那两个出现了奇数次的数字
因为 a != b ，则 eor != 0 ，所以 eor 肯定有某一个二进制位是 1
我们取 eor 二进制最右边的 1： int rightOne = eor & (~eor + 1)
文章图片
通过 rightOne 可以将数字串拆成两部分：cur & rightOne = 0 和 cur & rightOne != 0
a、b 分别落在两侧，其他偶数个的数字只会落在某一侧，整个数字串就被拆分成两个找出一串数字中唯一出现了奇数次的数字的数据模型了
分别从两侧中找出奇数次的数字即可
文章图片
完整代码如下
文章图片
这个解法没那么好理解，大家好好琢磨琢磨
总结
1、 XOR 用来判断同位上的值是否不同
2、 出现奇数个 、 偶数个 、 缺失的 、 重复的 字眼，可以往 XOR 考虑
3、关于 不用额外的变量交换两个变量的值，大家了解就好，不推荐使用
阅读性差，另外相比临时变量，它可能会出问题
4、示例代码地址
ExclusiveORTest
参考
That XOR Trick
推荐阅读
- 热闹中的孤独
- JAVA（抽象类与接口的区别&重载与重写&内存泄漏）
- 放屁有这三个特征的，请注意啦！这说明你的身体毒素太多
- 一个人的旅行，三亚
- 布丽吉特，人生绝对的赢家
- 慢慢的美丽
- 尽力
- 一个小故事，我的思考。
- 家乡的那条小河
- 《真与假的困惑》???|《真与假的困惑》??? ——致良知是一种伟大的力量