文章目录 *按位异或"^"(1)何为“^”：①“^”的介绍 (2)用于算法的经典案例： 1.数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？（源自leetcode面试题 17.04. 消失的数字） 2.一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。（源自leetcode.剑指 Offer 56 - I. 数组中数字出现的次数）①思路：②解题代码： 3.在不开辟新空间的前提之下，交换两个变量的值，例如，再不开辟新空间的前提下，a=3,b=4，交换a，b的值。①思路：运用规律二即可。②解题代码： (4)总结一番！：①异或运算的规律：

*按位异或"^" (1)何为“^”： ①“^”的介绍

* “ ^ ”的异或指的是二进制中，对应的对应二进制位相同时异或为零，相异时异或为一 让1^2，它的结果是什么呢？ 二进制形式下，异或的过程就是：左为异或前的1 、2右为异或结果。

规律一：这里我们也可看出，大小相同的数字异或结果一定为0，而0与任何数字进行异或大小不会改变。********************比如3 ^ 3=0, 3 ^ 0=3.(可以动笔试试2333) 规律二：自反性：其实就是用规律一推出A^B^B=A，那它本质上就是大小相同的数字异或结果为0 (2)用于算法的经典案例：

现在我们知道了二进制的异或原理，那么我们可以用它来解决什么问题呢？别急，这就放上几个经典例题：

1.数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？（源自leetcode面试题 17.04. 消失的数字）

题意为，给你一个0~n的不重复的无序整形数组，找到其中缺少的数字

举个栗子~ 给数组nums=[3,1,0] 要你通过算法输出[2] ；

好，现在我们就用异或的简单原理来解决这个问题： 首先，我们先来找找这个异或有无规律可循， 那么我们就在草稿本上奋笔疾书一番：

发现1^2=3——1^2^3=0——1^2^3^4=4——1^2^3^4^5=1——1^2^3^4^5^6=7——1^2^3^4^5^6^7=0——1^2^3^4^5^6^7^8=8——1^2^3^4^5^6^7^8^9=1。看到这里，相信你们一定有个想法是吧！，没错，笔者奋笔疾书，发现了个寂寞！！！ 但是！！！咱还是有其它灵感的，就是这些二进制运算是否能和加乘法一样符合结合律和交换律呢？ 答案是肯定的，以[0，1，2，3，4]为例，1^2^3^4=4,而3^2^1^0=4(不信可以在纸上试试呢！)好的，这样我们又发现第二条规律。 规律三：二进制的异或运算符合结合律和交换律

做了这么多前戏，终于可以开始解题了（泪目）…… 由规律二可知0~n它的异或结果是个定值，且它们的异或不分先后顺序，那我们就把0 ~ n的所有数字全部异或一遍先，再和题目给定数组nums中的数字进行异或，我们从规律一知道，相同数字异或会等于0，由此便可获得缺少的那个数字，用图表示它的原理大概就是这样：

解题代码： 让我们一鼓作气，再来个进阶训练：

2.一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。（源自leetcode.剑指 Offer 56 - I. 数组中数字出现的次数）

题意明确，就是让我们从给定的一堆整形数组中找出只出现一次的两个数字。

①思路： 假设只出现一次的数字为x , y (1)让给定数组nums每个元素依次异或（由规律二、三中的自反性和无序性知，出现两次的数字最终都被异或为0，最终的异或结果为两个只出现一次的数字的异或结果) （2）找到分离x,y的区别点（在（1）中我们已经获得这两个只出现一次的数字的异或结果，然后我们就要想办法分离出他们。我们知道，如果在一组数组中，只出现一次的数字只有一个的时候，让数组内的元素自己异或，由于异或的自反性，它最终的异或结果就是那个只出现一次的数字，所以我们先找到它们的区别点

可看到，二进制异或结果为1时，x,y的二进制形式在该位一定不同，分别为0，1（不同异或才为1嘛~）那么我们可将原数组中的元素分为两派，第一派是其二进制形式指定位处为1的数字；第二派则是其二进制形式指定位处为0的数字.指定位可任意找，我则是由地位向高位找，具体看代码即可知道） (3)由二我们可获的两派，分别让这两派的数字自行异或，即可获得x,y。 ②解题代码： #include<stdio.h> #include<stdlib.h> int* singleNumbers(int* nums, int numsSize, int* returnSize) { int ret = 0;//只出现一次的两个数的异或结果 int x = 0;//出现一次的数 int y = 0;//出现一次的数 int j = 0; for (int i = 0; i < numsSize; i++) { ret = ret ^ nums[i];//出现两次的数字异或为零，只剩下出现一次数字异或后的结果 } for (; j < 32; j++) { if (ret & (1 << j))//找到出现一次数组的分离位j(可将原数组分为两组：第j位为0的为一组；第j为为1的为一组) break; } for (int k = 0; k < numsSize; k++) { if (nums[k] & (1 << j)) { x = x ^ nums[k];//出现两次的数异或为0，只剩x } else { y = y ^ nums[k];//出现两次的数异或为0，只剩y } } int* arr = (int*)malloc(sizeof(int) * 2); arr[0] = x; arr[1] = y; *returnSize = 2; return arr; }

相信你做完上面两道例题后，对异或的性质已经有熟练掌握了，那么下面这道例题你能否独立完成呢？

3.在不开辟新空间的前提之下，交换两个变量的值，例如，再不开辟新空间的前提下，a=3,b=4，交换a，b的值。 ①思路：运用规律二即可。 ②解题代码： int main() { int a = 3; int b = 4; a = a ^ b; b = b ^ a;//由自反性质和交换律可得b==b^a^b==a a = a ^ b;//a==a^b^a==b; return 0; } (4)总结一番！： ①异或运算的规律： 规律一：这里我们也可看出，大小相同的数字异或结果一定为0，而0与任何数字进行异或大小不会改变。********************比如3 ^ 3=0, 3 ^ 0=3.(可以动笔试试2333) 规律二：自反性：其实就是用规律一推出A^B^B=A，那它本质上就是大小相同的数字异或结果为0 规律三：二进制的异或运算符合结合律和交换律*************************************************

---

1.本站遵循行业规范，任何转载的稿件都会明确标注作者和来源；2.本站的原创文章，会注明原创字样,如未注明都非原创，如有侵权请联系删除！；3.作者投稿可能会经我们编辑修改或补充；4.本站不提供任何储存功能只提供收集或者投稿人的网盘链接。