一、位运算

提示

位运算是计算速度最快的

（一）移位

1.>> 右移

• 相当于 /2

2.<< 左移

• 相当于 *2

（二）异或运算

1.性质

• 0 ^ N = N
• N ^ N = 0
• 满足交换律：a ^ b = b ^ a
• 满足结合律：a ^ b ^ c = a ^ (b ^ c)

2.不使用额外空间交换两个变量的值

• 只适用于整形类型的数组
• a 和 b 相等时会报错

const swap = (arr, a, b) => {
  arr[a] = arr[a] ^ arr[b]; // a: a ^ b; b: b
  arr[b] = arr[a] ^ arr[b]; // a: a ^ b; b: a ^ b ^ b => a
  arr[a] = arr[a] ^ arr[b]; // a: a ^ b ^ a => b; b: a
};

3.找出数组中仅出现一次的数字

• 利用异或运算满足交换律和结合律的性质
• 初始变量 eor 值为 0，异或遍历数组
• 数组中出现偶数次的数，异或遍历后都为 0
• 最后 eor 保存的值就是仅出现一次的数字

const arr = [1, 2, 3, 1, 2, 3, 4, 5, 6, 4, 5, 6, 7];
let eor = 0;
for (let i = 0; i < arr.length; i++) {
  eor ^= arr[i];
}
console.log(eor); // 7

4.找出数组中仅出现一次的两个不同的数字

• 异或遍历数组，得到两个不同的数字的异或结果，保存到 eor 中
• eor 的二进制形式，如果某一位为 1，说明 a 和 b 在该位置上不相等
• 只要找到 1 的某一个位置，异或遍历数组后必定能将整个数组分为两部分
  • 一部分在该位置上是 0
  • 一部分在该位置上是 1
  • a 和 b 必定不在同一部分
  • 每个部分除了 a、b 外的数都是出现偶数次的数字
• 任一部分异或遍历后就能将偶数次的数字化为 0，剩下 a（b）
• 最后利用 eor 和得到的数字异或，就能得到 b（a）

const arr = [1, 2, 3, 1, 2, 3, 4, 5, 6, 5, 6, 7];
let eor = 0;
for (let i = 0; i < arr.length; i++) {
  eor ^= arr[i];
}

/**
 * 已知 eor = a ^ b 且 eor !== 0
 * 则eor必然有一个位置上是1
 * 使用以下方式提取出最右侧的1
 */
let rightOne = eor & (!eor + 1);

let onlyOne = 0; // eor
for (let cur of arr) {
  if ((cur & rightOne) === 1) {
    onlyOne ^= cur;
  }
}
console.log(onlyOne, eor ^ onlyOne); // 7 4