二进制的一些小技巧

^

• 找到汉明距离（两个数对应二进制位不同的数目）；

  汉明距离是使用在数据传输差错控制编码里。

(num - 1) & num

• 用于清除 num 最右边的 1；

Brian Kernighan（布莱恩 柯林汉） 算法是一种用于统计一个二进制数中 1 的个数的算法，通过不断将数字中的最低位的 1 变成 0 的方式统计二进制数中的 1 的个数。

num & 1

• 用于判断 num 的二进制表示中最右边的位是否为 1；

num >> 1

• 用于将 num 的二进制表示向右移动一位；

(1 << n) - 1

• 生成一个长度为 n 并且全为 1 的二进制数；

  用于使用异或快速将一个数进行取反， 如果直接取反一个数的话得到的是负数。

(1 << k) & n

k 从 30 开始递减。

• 用于比较一个二进制数的高位是否为 1。

快速构造小于 num 的 2 的幂次方的数组

const num = 15; // 最多为 2^3，也就是 8

let x = num;
const ans = [];
while (x > 0) {
  ans.push(lowbit(x));
  x -= lowbit(x);
}

function lowbit(x) {
  return x & -x;
}

异或前缀和

一个子数组的异或和（i, j）= 异或前缀和（j + 1）^ 异或前缀和（i）

异或前缀和数组比原数组长度多 1，多了一个 0.