1.Java异或介绍

异或是一种基于二进制的位运算，用符号XOR或者 ^ 表示，其运算法则是对运算符两侧数的每一个二进制位，同值取0，异值取1。
异或满足交换律和结合律，即：
1）交换律（即a^b == b^a）
2）结合律（即(a^b)c == a^(bc)）
3）对于任何数x，都有x^x=0，x0=x
4）自反性 A XOR B XOR B = A XOR 0 = A

2异或的实际使用场景

1）不使用临时变量和临时的存储空间，交换两个变量

　int a = 10, b = 5；

  a = a ^ b;

  b = a ^ b;

  a = a ^ b;

2）找寻重复元素

问题1：1-1000放在含有1001个元素的数组中，只有唯一的一个元素值重复，其它均只出现一次。每个数组元素只能访问一次，设计一个算法，将它找出来；不用辅助存储空间，能否设计一个算法实现？
最简单做法，肯定是把数组累计相加，然后减去1~1000的和，即为重复元素，但是题意中声明了，不可以用辅助的存储空间，我们严格要求的话，这种解法就不满足了。
此时可以想到用异或

我们假设数组异或结果为 1²3...^1000 = T （此时的T中包含两个n），那么根据结合律和自反律，T^n 实际上就是1~1000的实际值的异或结果，原因的话，很简单，T中的两个n异或之后为0，也就是说T中已经没有n了，所以 T^n == 1~1000的实际值的异或结果

由上面的推导可知，我们把T再和1~1000的异或结果 去异或，则为所求的结果n

问题2：一个数组存放若干整数，一个数出现奇数次，其余数均出现偶数次，找出这个出现奇数次的数？
这个题相对来说简单很多了，其实就是利用异或的自反和结合律即可解答，偶数次出现的数异或肯定为0，所以最终数组所有值异或的结果就是那个奇数出现的数字