*按位异或"^"

(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==aa = a ^ b;//a==a^b^a==b;return 0;
}

(4)总结一番！：

①异或运算的规律：

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