位运算 n & n-1

  n&(n-1)作用：将n的二进制表示中的最低位为1的改为0

  例如 20 & 19 = 16 => 10100 & 10011 => 10000

  21 & 20 = 20 => 10101 & 10100 => 10100

  因此对于奇数来说，就是把它最后一位的 1 给抹去，相当于减了一个 1；

  而对于偶数来说，就是除了一个 2^x ，也就是把最低位的 1 给抹去了。

用途 1 ：判断一个数是否是 2 的幂次方

  使用 n & (n-1) === 0 可以判断 n 是否是 2 的幂次方。

  根据上面的分析，若 n 是偶数，则 n & (n-1) 会将最低位的 1 抹去，而对于 2 的幂次方，二进制表示中只有一个 1，如 8 = 1000 ， 16 = 10000 ，因此抹去最低位的 1 的话 n & (n-1) 就会变成 0 了。

用途2：计算一个数的二进制中有多少个 1

LeetCode 实际应用

  因为 n & (n-1) 每次能够消除最低位的 1 ，因此可以使用以下代码计算 n 中的二进制个数：

while (n) {
    count++;
    n & n - 1;
}

位运算 x & -x

  x & -x 的作用是得到最低位的 1 。

  例如 7 & -7，假设一个数字占用 4 个 bit，那么 7 的二进制是 0111 ，则 -7 的二进制就是 1001 （反码加 1），则 0111 & 1001 = 0001 ，就得到了最低位的 1

  再例如 6 & -6，同样，设一个数字占用 4 位，那么 6 => 0110，-6 => 1010，则 0110 & 1010 = 0010，得到了最低位的 1。

位运算异或 ^

  若一个数组中只有一个数字只出现了一次，其余数字都出现了两次，那么使用异或操作能够一次遍历找到这个数字，且空间复杂度为 O(1)。

  比如三个数字：5, 3, 5 ，首先 5 = 101, 3 = 011 ，那么 101 ^ 011 = 110，110 ^ 101 = 011 = 3 ，对 5 进行了两次异或，相当于又恢复了原先的数字 3

LeetCode 实际运用