位运算_异或

原理

相同的数异或为0，不同的异或为1。0和任何数异或等于这个数本身。

性质

交换律
结合律（即(a^b)^c == a^(b^c)）
对于任何数x，都有x^x=0，x^0=x
自反性 A XOR B XOR B = A xor 0 = A —> A XOR B = C 则 C XOR B = A

例子

1-1000放在含有1001个元素的数组中，只有唯一的一个元素值重复，其它均只出现
一次。每个数组元素只能访问一次，设计一个算法，将它找出来；不用辅助存储空
间，能否设计一个算法实现？

1
2
3
4

解法一:遍历所有和结果减去1-1000即可，但是不是最优解,而且过大可能溢出

解法二:异或就没有这个问题，并且性能更好。
将所有的数全部异或，得到的结果与1^2^3^...^1000的结果进行异或，得到的结果就是重复数。

如果除了一个数字以外，其他数字都出现了两次，那么如何找到出现一次的数字？

1
2
3

答案很简单：全员进行异或操作即可。考虑异或操作的性质：对于两个操作数的每一位，相同结果为 00，
不同结果为 11。那么在计算过程中，成对出现的数字的所有位会两两抵消为 00，
最终得到的结果就是那个出现了一次的数字。

扩展

那么这一方法如何扩展到找出两个出现一次的数字呢？

如何扩展到从两个数字相同到存在3个相同数字？

相关题目