异或操作的应用

发表于 分类于

基本规则

  1. 异或操作满足交换律和结合律
  2. 0^N = N
  3. N^N = 0

用于交换两个数

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * @Description: 使用异或操作实现交换，
 * 但是a和b不能相等，否则两者的数据都会被洗成0
 * @param {*} a
 * @param {*} b
 * @return {*}
 */
function swapByEor (a, b) {
  a = a ^ b
  b = a ^ b
  a = a ^ b
}

找出数组中唯一一个出现奇数次的数

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * @Description: 找出数组中唯一一个出现奇数次的数
 * @param {*} arr
 * @return {*}
 */
function findOddTimesNum (arr) {
  let eor = 0
  for (let item of arr) {
    eor ^= item
  }
  return eor
}

找出数组中唯二的出现奇数次的两个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @Description: 找出数组中唯二的出现奇数次的两个数
 * @param {*} arr
 * @return {*}
 */
function findOddTimesNum2 (arr) {
  let eor = 0
  for (let item of arr) {
    eor ^= item
  }
  //找出最右侧不等于1的那一位
  let eor1 = eor & (~eor + 1)
  let num1 = 0
  for (let item of arr) {
    if (eor1 & item) {
      num1 ^= item
    }
  }
  let num2 = eor ^ num1
  return [num1, num2]
}