摘要：开心一刻两头奶牛在一起吃草，其中一头奶牛甲越吃越慢，一副若有所思的模样，另一头奶牛奶牛乙发觉了，开始了对话奶牛乙搁那合计啥呢奶牛甲你帮我合计合计奶牛乙咋地了奶牛甲我吃的是草，挤出来的是奶，也就是说我把没用的变成有用的了奶牛乙是这个事奶牛甲人
两头奶牛在一起吃草，其中一头（奶牛甲）越吃越慢，一副若有所思的模样，另一头奶牛（奶牛乙）发觉了，开始了对话
奶牛乙：搁那合计啥呢？
奶牛甲：你帮我合计合计
奶牛乙：咋地了
奶牛甲：我吃的是草，挤出来的是奶，也就是说我把没用的变成有用的了
奶牛乙：是这个事
奶牛甲：人呢，喝的是奶，拉出来的是粑粑
奶牛乙：咋地了
奶牛甲：他又把有用的变成没用的了，我这不白干了吗
奶牛乙：你说的不对
奶牛甲：不对吗？
奶牛乙：那粑粑做成化肥，有化肥才能长草，所以说你吃的不是草，是粑粑
奶牛乙：啊 ？？？
关于“位”运算，大家或多或少都知道点，比如与运算（&）、或运算（|）、异或运算（^）、取反运算（~）、左移（<<）、右移（>>）
因为今天的主角是：异或运算，其他的位运算就不在本文展开了，大家自行去查阅
异或运算的英文名： 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 表示任何值，也就是说：两个相等的值做异或运算，得到的结果是 0
因为值相等，那么值对应的各个位的值也是相等的，对应到 XOR 的运算真值表则是
我们来看个具体的例子：15 ^ 15
15 对应的二进制位： 01111 ，那么 15 ^ 15 的运算则是
一个值与 0 做异或运算，得到的结果仍是这个值
例如：15 ^ 0 = 15
同加法有交换律、乘法也有交换律一样，异或运算也有交换律
例如：15 ^ 8 = 8 ^ 15
同加法有结合律、乘法有结合律一样，异或运算也结合律
例如：(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
问题详细描述：一串数字包含 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
那么得到的结果就是缺少的那个数
不存在溢出的风险，并且位运算比加、减运算更快
问题详细描述：一串数字包含 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、示例代码地址
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/125681.html
摘要：并且，一些伪元素可以使开发者获取到不存在于源文档中的内容比如常见的还可以为伪元素定制样式。。中新增加的伪元素必须用伪类使用一个冒号例如。就本文而言，我们将把我们探讨的范围限制在和这两个伪元素的巧用上。 作为一门前端er,你肯定熟知 a:hover a:visited.....我还记得在小本本上记着诀窍：love 与 hate 纠缠不休,大家都懂的吧。。。。 伪类和...
摘要：选择排序算法实现实现选择排序，记录最小元素的索引，最后才交换位置说明交换两个数组中的元素，在中有更简单的写法，这是的语法糖，其它语言中是没有的。和语言中比较器的实现前面我们说到了，我们为了突出排序算法的思想，将所有的例子仅限在数组排序中。 showImg(https://segmentfault.com/img/remote/1460000017909538?w=1949&h=1080...
摘要：位算法的效率有多快我就不说，不信你可以去用亿个数据模拟一下，今天给大家讲一讲位运算的一些经典例子。不过，最重要的不是看懂了这些例子就好，而是要在以后多去运用位运算这些技巧，当然，采用位运算，也是可以装逼的，不信，你往下看。位算法的效率有多快我就不说，不信你可以去用 10 亿个数据模拟一下，今天给大家讲一讲位运算的一些经典例子。不过，最重要的不是看懂了这些例子就好，而是要在以后多去运用位运算这...
阅读 3311·2023-01-11 11:02
阅读 3884·2023-01-11 11:02
阅读 2717·2023-01-11 11:02
阅读 4895·2023-01-11 11:02
阅读 4400·2023-01-11 11:02
阅读 5110·2023-01-11 11:02
阅读 4891·2023-01-11 11:02
阅读 3370·2023-01-11 11:02
