keren的笔记
0%

异或操作及应用

发表于

异或百度百科。异或操作相同为0，不同为1，时间长了很容易就忘记，辛得高人指点，有了另外一种记忆方式：异或即为相同位相加无进位。如1^1，舍弃进位即为0；1^0即为1。

1、运算法则

  • a^a=0。
  • a^0=a。
  • a^b=b^a。
  • a^b^c=(a^b)^c=(a^c)^b=a^(b^c)。
  • a^b^a=b。

根据上面的这些运算法则，可以运用到下面的一些算法题中。

2、两个变量交换

问题：不申请额外的变量实现交换两个变量。

1
2
3
4
5
6
7
public void swap(int a,int b) {
  a=a^b;
  // b=(a^b)^b=a
  b=a^b;
  // a=(a^b)^a
  a=a^b;
}

3、数组中一个出现奇数次的数字

问题：一个数组中有一个数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这个数。

1
2
3
4
5
6
7
8
9
10
public void findNumberAppearOddTimes(int[] arr) {
  if(arr==null || arr.length==0) {
    return;
  }
  int xor = 0;
  for(int i=0;i<arr.length;i++) {
    xor ^= arr[i];
  }
  System.out.println(xor);
}

4、数组中两个出现奇数次的数字

问题：一个数组中有两个数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这两个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public void findNumberAppearOddTimes(int[] arr) {
  if(arr==null || arr.length==0) {
    return;
  }
  int xor = 0;
  for(int i=0;i<arr.length;i++) {
    xor ^= arr[i];
  }
  // 1、运行到此可以知道：假如出现奇数次的两个数为a和b，则xor=a^b。
  // 2、xor！=0可推导出：xor在第i位二进制位上为1，
  // 则a和b一定存在第i位二进制位上不相同,要么a的第i位二进制位上为1，要么b的第i位二进制位上为1。
  // 3、此时可以将arr中的数分为两类：第i位二进制上为1的数，第i位二进制位上不位1的数。
  // 4、只接寻找xor二进制位最右侧的1：int rightOne=xor&(~xor+1);
  int rightOne=xor&(~xor+1);
  int xor1=0;
  for(int i=0;i<arr.length;i++) {
    // 数组中数&rightOne !=0 为第i位二进制上为1的数
    if(arr[i]&rightOne!=0) {
      // 最终结果为其中一个出现奇数次的数
    	xor1 ^= arr[i];
     }
  }
  // xor和xor1再进行异或操作即得到另外一个出现奇数次的数
  System.out.println(xor1+":"+xor1^xor);
}