奇妙的算法知识

位运算 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 = 100016 = 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 = 110110 ^ 101 = 011 = 3 ,对 5 进行了两次异或,相当于又恢复了原先的数字 3

LeetCode 实际运用


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!

 目录