位运算

为什么需要位运算

机器里的数字表示方式和存储格式就是二进制。
计算机大部分都是高电位和低电位,它本身任何一个整型或者十进制的数,在计算机里面的数字表示方式和存储形式都是二进制

4(d):0100 8(d):01000 5(d):0101 6(d):0110

十进制转二进制:余数短除法除以二

一直往下除,直到商为 0 为止。把每个新的商数除以二,然后把余数写在被除数的右边。直到商数为 0 为止。

位运算符

含义 运算符 示例
左移 << 0011 => 0110
右移 >> 0110 => 0011
按位或:只要一个二进制为1,与出来就是1 | 0011 | 1011 => 1011
按位与:只要一个二进制为0,与出来就是0 & 0011 & 1011 => 0011
按位取反 ~ 0011 => 1100
按位异或(相同为零不同为一):相异就是 1,相同就是 0 ^ 0011 ^ 1011 => 1000

异或

异或:相同为 0,不同为 1。也可用 “不进位加法” 来理解。

异或操作的特点:

x ^ 0 => x x ^ 1s => ~x // 1s = ~0 x ^ (~x) => 1s x ^ x => 0 c = a ^ b => a ^ c = b,b ^ c = a // 交换两个数 a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c // associative

指定位置的位运算

  • 将 x 最右边的 n 位清零:x & (~0 << n)
  • 获取 x 的第 n 位值(0 或者 1):(x >> n) & 1
  • 获取 x 的第 n 位的幂值:x & (1 << n)
  • 仅将第 n 位置为 1:x | (1 << n)
  • 仅将第 n 位置为 0:x & (~(1 << n))
  • 将 x 最高位至第 n 位(含)清零:x & ((1 << n) - 1)

位运算要点

  • 判断奇偶
    • x % 2 == 1 => x & 1 == 1
    • x % 2 == 0 => x & 1 == 0
  • x >> 1 => x / 2
    • x = x / 2 => x = x >> 1
    • mid = (left + right) / 2 => mid = (left + right) >> 1
  • x = x & (x - 1) 清零最低位的 1
  • x & -x => 得到最低位的 1
  • x & ~x => 0
  • !!~(x) 判断下标是否存在
    • !!~“xx”.indexOf(x)

相关题目

位1的个数

2的幂

颠倒二进制位

N 皇后

N皇后 II

// 位1的个数 /** * @param {number} n - a positive integer * @return {number} */ var hammingWeight = function(n) { let sum = 0; while (n != 0) { sum++; n &= (n - 1); } return sum; };
// 2的幂 // 这个数的表示形式,有且仅有二进制位是 1 /** * @param {number} n * @return {boolean} */ var isPowerOfTwo = function(n) { return n > 0 && (n & (n - 1)) == 0; };
// 颠倒二进制位 /** * @param {number} n - a positive integer * @return {number} - a positive integer */ var reverseBits = function(n) { let ans = 0; for (let i = 0; i < 32; i++) { ans = (ans << 1) + (n & 1); n >>= 1; } return ans >>> 0; };

比特位计数

// 比特位计数 // 位运算 + DP /** * @param {number} n * @return {number[]} */ var countBits = function(n) { const ans = new Array(n + 1).fill(0); for (let i = 1; i <= n; i++) { ans[i] = ans[i & (i - 1)] + 1; } return ans; };