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

异或运算

文章目录

• • • 异或运算
  • @[toc]
  • • • 1.基础位运算
      • • 按位与 `&`
        • 按位或 `|`
        • 按位异或 `^`
        • 按位取反 `~`
      • 2.异或运算的性质（重点）
      • 3.基于异或运算的常用算法
      • • 算法1：交换两数
        • 算法2：提取某个数二进制上最右的1
      • 4.例题

1.基础位运算

按位与&

规则：两位全1才得1，有0则0

0&0=0 0&1=0 1&0=0 1&1=1

按位或|

规则：有1就为1，全0才0

0|0=0 0|1=1 1|0=1 1|1=1

按位异或^

规则：相同为 0，不同为 1

0^0=0 0^1=1 1^0=1 1^1=0

按位取反~

规则：所有二进制位 0、1 翻转

2.异或运算的性质（重点）

异或运算符：^

运算规则（按二进制每一位单独计算）：

• 相同为 0，不同为 1
  • 0 ^ 0 = 0
  • 0 ^ 1 = 1
  • 1 ^ 0 = 1
  • 1 ^ 1 = 0

例如：

print(3^5)# 3 二进制：011# 5 二进制：101# 异或结果：110 → 6

设 a、b 为任意整数：

1. 自异或清零：a ^ a = 0
2. 任何数异或 0 不变：a ^ 0 = a
3. 交换律：a ^ b = b ^ a
4. 结合律：(a ^ b) ^ c = a ^ (b ^ c)
5. 消去性质：a ^ b ^ a = b

3.基于异或运算的常用算法

算法1：交换两数

a=4b=3a=a^b b=a^b a=a^bprint(a,b)# 结果：3， 4

但是在python里面直接用a, b = b, a就好了。

算法2：提取某个数二进制上最右的1

defrightone(a):return(~a+1)&aprint(rightone(6),rightone(10),rightone(7),rightone(8))#结果2218

6 → 110，输出2

10 → 1010，输出2

7 → 0111，输出1

8 → 1000，输出8

4.例题

给定一组整数数组：

1. 情况 1：仅有一种数出现奇数次，其余所有数都出现偶数次

   要求找出这个唯一出现奇数次的数字。

   （思路：相同数异或结果为0，0异或任意数等于它本身，把数组所有数依次异或，最终结果就是这个出现奇数次的数）

   deffindnumber(mylist):a=0foriinmylist:a=a^ireturnaprint(findnumber([3,3,3,3,4,4,5,5,5,2,2]))# 结果：5

2. 情况 2：有两种不同的数各自出现奇数次，其余所有数都出现偶数次

   要求找出这两个出现奇数次的数字。

   （思路：如果把全部数异或会得到这两个数的异或值（因为是两种不同的数，异或结果一定非0，那么这两个数一定在二进制某位上不同），找到异或结果二进制里某一位为1的位置（说明这一位上这两个数二进制数不同，按这一位把数组分成两组（这一位上是1的一组，是0的一组），两个目标数一定会被分到不同组，每组内部再分别全员异或，就能分别求出两个目标数。

   deffind_number(mylist):a=0c=0foriinmylist:a=a^i b=(~a+1)&aforjinmylist:ifj&b==b:c=c^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]c=c^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]