Python异或运算符示例

​

 目录

异或

异或的性质

示例1：值交换

示例2：找出现一次的元素

示例2代码： 

异或

英文为exclusive OR，缩写成xor，符号是^

异或的性质

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)

代码演示：

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代码： 

arr = [4, 1, 2, 1, 2]
index = 0
for i in arr:
    index ^= i
print(index)

结果： 

​编辑

自定义测试：

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)

结果正确：