目录
异或
异或的性质
示例1：值交换
示例2：找出现一次的元素
示例2代码：
异或
英文为exclusive OR，缩写成xor，符号是^
a | b | a^b |
|---|---|---|
0假 | 0假 | 0假 |
0假 | 1真 | 1真 |
1真 | 0假 | 1真 |
1真 | 1真 | 0假 |
异或的性质
1、a ^ a=0 任何数字和自己异或结果是0 2、a ^ 0=a 任何数字和0异或还是他自己 3、a ^ b = b ^ a 异或运算具有交换律 4、a ^ (b ^ c) = (a ^ c) ^ b 异或运算具有结合律
我们依赖这四条性质就能做很多操作，例如下面的两个示例：
示例1：值交换
x=5 y=7将两个变量的值通过异或运算符进行交换
x = 5 y = 7 # x = 101(二进制) ^ 111(二进制) = 010(二进制) 异或代表相同取反，不同取正 1:1-0:1-1:1 = 010 二进制的010等于10进制的2 x = x ^ y # y = 010(二进制) ^ 111(二进制) = 101(二进制) 也就是：0:1-1:1-0:1 = 101 二进制101等于10进制的5 y = x ^ y # x = 010(二进制) ^ 101(二进制) = 111(二进制) 也就是：0:1-1:0-0:1 = 111 二进制的111等于10进制的7 x = x ^ y # 最终输出x = 111(二进制) = 7(十进制) print(x) # y = 101(二进制) = 5(十进制) print(y)
代码演示：
代码语言：javascript复制x = 5
y = 7
# x = 101(二进制) ^ 111(二进制) = 010(二进制) 异或代表相同取反，不同取正 1:1-0:1-1:1 = 010 二进制的010等于10进制的2
x = x ^ y
# y = 010(二进制) ^ 111(二进制) = 101(二进制) 也就是：0:1-1:1-0:1 = 101 二进制101等于10进制的5
y = x ^ y
# x = 010(二进制) ^ 101(二进制) = 111(二进制) 也就是：0:1-1:0-0:1 = 111 二进制的111等于10进制的7
x = x ^ y
# 最终输出x = 111(二进制) = 7(十进制)
print(x)
# y = 101(二进制) = 5(十进制)
print(y)输出结果：
示例2：找出现一次的元素
给定一个非空整数数组，除了某个元素只出现一次以外，其每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗?
输入示例1：
[2,2,1]
输出示例1：
1
输入示例2：
[4,1,2,1,2]
输出示例2：
4
理解分析：
我们在异或运算的过程中根据异或门的逻辑来看，因为数都是成对的，那么成对的数在异或过程中都会被消耗掉，只有单独存在的一个数不会被配对消耗掉，故而可以留存到最后。
注：
这里主要用到的是异或的n ^ n = 0的性质，来逐一消耗成对的数。
示例2代码：
代码语言：javascript复制arr = [4, 1, 2, 1, 2]
index = 0
for i in arr:
index ^= i
print(index)结果：
自定义测试：
代码语言：javascript复制arr = [4, 1, 2, 3, 1, 2, 3, 1, 2, 3, 2, 1, 2, 3, 4, 666, 1, 2, 3, 2]
index = 0
for i in arr:
index ^= i
print(index)结果正确：
