Python异或运算符示例
目录
异或
异或的性质
示例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)
代码演示:
x = 5y = 7# x = 101(二进制) ^ 111(二进制) = 010(二进制) 异或代表相同取反,不同取正 1:1-0:1-1:1 = 010 二进制的010等于10进制的2x = x ^ y# y = 010(二进制) ^ 111(二进制) = 101(二进制) 也就是:0:1-1:1-0:1 = 101 二进制101等于10进制的5y = x ^ y# x = 010(二进制) ^ 101(二进制) = 111(二进制) 也就是:0:1-1:0-0:1 = 111 二进制的111等于10进制的7x = 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 = 0for i in arr: index ^= iprint(index)
结果:
自定义测试:
arr = [4, 1, 2, 3, 1, 2, 3, 1, 2, 3, 2, 1, 2, 3, 4, 666, 1, 2, 3, 2]index = 0for i in arr: index ^= iprint(index)
结果正确: