【算法与数据结构】异或运算

异或运算文章目录异或运算[toc]1.基础位运算按位与 按位或 |按位异或 ^按位取反 ~2.异或运算的性质重点3.基于异或运算的常用算法算法1交换两数算法2提取某个数二进制上最右的14.例题1.基础位运算按位与规则两位全1才得1有0则0000 010 100 111按位或|规则有1就为1全0才00|00 0|11 1|01 1|11按位异或^规则相同为 0不同为 10^00 0^11 1^01 1^10按位取反~规则所有二进制位 0、1 翻转2.异或运算的性质重点异或运算符^运算规则按二进制每一位单独计算相同为 0不同为 10 ^ 0 00 ^ 1 11 ^ 0 11 ^ 1 0例如print(3^5)# 3 二进制011# 5 二进制101# 异或结果110 → 6设 a、b 为任意整数自异或清零a ^ a 0任何数异或 0 不变a ^ 0 a交换律a ^ b b ^ a结合律(a ^ b) ^ c a ^ (b ^ c)消去性质a ^ b ^ a b3.基于异或运算的常用算法算法1交换两数a4b3aa^b ba^b aa^bprint(a,b)# 结果3 4但是在python里面直接用a, b b, a就好了。算法2提取某个数二进制上最右的1defrightone(a):return(~a1)aprint(rightone(6),rightone(10),rightone(7),rightone(8))#结果22186 → 110输出210 → 1010输出27 → 0111输出18 → 1000输出84.例题给定一组整数数组情况 1仅有一种数出现奇数次其余所有数都出现偶数次要求找出这个唯一出现奇数次的数字。思路相同数异或结果为00异或任意数等于它本身把数组所有数依次异或最终结果就是这个出现奇数次的数deffindnumber(mylist):a0foriinmylist:aa^ireturnaprint(findnumber([3,3,3,3,4,4,5,5,5,2,2]))# 结果5情况 2有两种不同的数各自出现奇数次其余所有数都出现偶数次要求找出这两个出现奇数次的数字。思路如果把全部数异或会得到这两个数的异或值因为是两种不同的数异或结果一定非0那么这两个数一定在二进制某位上不同找到异或结果二进制里某一位为1的位置说明这一位上这两个数二进制数不同按这一位把数组分成两组这一位上是1的一组是0的一组两个目标数一定会被分到不同组每组内部再分别全员异或就能分别求出两个目标数。deffind_number(mylist):a0c0foriinmylist:aa^i b(~a1)aforjinmylist:ifjbb:cc^jreturn[c,a^c]print(find_number([3,3,3,3,4,4,5,5,5,2,2,1,1,1,1,1]))# 结果[5, 1]cc^jreturn[c,a^c]print(find_number([3,3,3,3,4,4,5,5,5,2,2,1,1,1,1,1]))# 结果[5, 1]