程序中的所有数在计算机内存中都是以二进制的形式存储的。位运算就是直接对整数在内存中的二进制位进行操作。由于位运算直接对内存数据进行操作，不需要转成十进制，因此处理速度非常快。

位运算操作符

符号	描述	运算规则
&	与	两个位都为 1 时，结果才为 1
|	或	两个位都为 0 时，结果才为 0
^	异或	两个位相同为 0，相异为 1
~	取反	0 变 1，1 变 0
<<	左移	各二进位全部左移若干位，高位丢弃，低位补 0
>>	右移	各二进位全部右移若干位，对无符号数，高位补 0，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补 0（逻辑右移）

异或的一些有用特性

x ^ 0 = x;
x ^ 1 = ~x;
x ^ ~x = 1;
x ^ x = 0;
(a ^ b = (c) => (a ^ c = b)), (b ^ c = a);
a ^ b ^ c = a ^ (b ^ c) = a ^ b ^ c;

实战常用的位运算操作

1. 判断奇偶性

x & (1 === 1); // 奇数
x & (1 === 0); // 偶数

这种操作比模运算会更快，因为模运算需要先进行一次除法运算，x % 2 === 1。

2. 清除最低位的 1

x = x & (x - 1);

3. 得到最低位的 1

x & -x;

比较复杂的位运算操作

1. 将 x 最右边的 n 位清零

x & (~0 << n);

2. 获取 x 的第 n 位值（0 或者 1）

(x >> n) & 1;

3. 获取 x 的第 n 位的幂值

x & (1 << (n - 1));

4. 仅将第 n 位置为 1

x | (1 << n);

5. 仅将第 n 位置为 0

x & ~(1 << n);

6. 将 x 的最高位至第 n 位（含）清零

x & ((1 << n) - 1);

7. 将第 n 位至第 0 位（含）清零

x & ~((1 << (n + 1)) - 1);

位 1 的个数

题目地址 (opens new window)

const hammingWeight = (n) => {
  let res = 0;
  for (let i = 0; i < 32; i++) {
    if ((n & (1 << i)) !== 0) {
      res++;
    }
  }
  return res;
};

const hammingWeight = (n) => {
  let res = 0;
  while (n) {
    res++;
    n &= n - 1;
  }
  return res;
};

2 的幂

题目地址 (opens new window)

const isPowerOfTwo = (n) => {
  return n > 0 && (n & (n - 1)) === 0;
};

const isPowerOfTwo = (n) => {
  return n > 0 && (n & -n) === n;
};

const isPowerOfTwo = (n) => {
  if (n < 1) return false;
  while (n !== 1) {
    if (n % 2 === 1) return false;
    n /= 2;
  }
  return true;
};

比特位计数

题目地址 (opens new window)

const countOnes = (x) => {
  let count = 0;
  while (x) {
    count++;
    x &= x - 1;
  }
  return count;
};
const countBits = (n) => {
  const arr = [];
  for (let i = 0; i <= n; i++) {
    arr.push(countOnes(i));
  }
  return arr;
};

const countBits = (n) => {
  const bits = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    bits[i] = bits[i & (i - 1)] + 1;
  }
  return bits;
};