位运算

  • 简介：程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算就是直接对整数在内存中的二进制位进行操作。常见的运算符有与(&)、或(|)、异或(^)、取反(~)、左移(<<)、右移(>>是带符号右移 >>>无符号右移动)。
  • 优点：可以直接对二进制数进行操作，执行速度比较快，而且可以节省内存空间，特别是在处理大规模数据时，优势更加明显。
  • 应用场景：常用于处理二进制数据，如位图压缩、哈希表实现、位集合操作等。也可以用于加密算法、图像处理、网络协议等领域。
  • 时间复杂度：通常是$O(1)$，因为它们直接对二进制位进行操作，而不需要循环或递归等复杂的计算过程。
  • 技巧：
    1. 按位与&：
      • 判断一个数的奇偶性（x & 1 == 0表示x是偶数，x & 1 == 1表示x是奇数）
      • 清零一个数的某一位(x &= ~(1 << n)表示将x的第n位清零)
      • 判断一个数是否是2的幂次方。例如：(x & (x - 1)) == 0 表示x是2的幂次方
      • Brian Kernighan算法：消除数字n的二进制表示中的最后一位1，也即计算汉明权重（Hamming Weight）：n & (n-1)
      • 取出 x 的二进制表示中最低位的1 ：x & -x
    2. 按位或|：
      • 将一个数的某一位设置为1 ( x |= (1 << n) 表示将x的第n位设置为1)
    3. 按位异或^：
      • 可以用来交换两个变量的值（a ^= b; b ^= a; a ^= b;）
      • 检查一个数是否出现了奇数次。对于数组中出现两次的数，使用异或操作可以找到它们，任何数和其自身做异或运算，结果是0，即 a ^ a = 0
      • 任何数和 0 做异或运算，结果仍然是原来的数，即 a ^ 0 = a
      • 异或运算满足交换律和结合律，即a ⊕ b ⊕ a = b ⊕ a ⊕ a = b ⊕ (a ⊕ a) = b ⊕ 0 = b
    4. 左移位<<：可以用来计算2的幂次方（1 << n表示2的n次方）
    5. 右移位>>：可以用来计算除以2的幂次方（x >> n表示将x除以2的n次方）
  • 常用方法：
    • bin()获取数字的二进制值
    • ord()输入单个字符返回其ASCII值（0-255）或unicode值
    • chr()输入一个整数[0，255]返回其ASCII值
    • int("s",x)将指定进制x的字符s转换成十进制值
    • 正数的反码和补码都与原码相同。负数的二进制用补码表示。负数的反码为对该数的原码除符号位外各位取反。负数的补码为对该数的原码除符号位外各位取反，然后在最后一位加1 。

Python 没有 int, long 等不同长度变量，即在编程时无变量位数的概念。

  • 获取负数的补码：需要将数字与十六进制数 0xffffffff 相与。可s理解为舍去此数字 32 位以上的数字（将 32 位以上都变为 00），从无限长度变为一个 32 位整数。
  • 返回前数字还原： 若补码 aaa 为负数（ 0x7fffffff 是最大的正数的补码 ），需执行 ~(a ^ x) 操作，将补码还原至 Python 的存储格式。 a ^ x 运算将 1 至 32 位按位取反； ~ 运算是将整个数字取反；因此， ~(a ^ x) 是将 32 位以上的位取反，1 至 32 位不变

参考博客：

力扣指南

位运算
题目 技巧 难度
✅67. 二进制求和 简直不是人想出来的！！！ 🌟
✅136. 只出现一次的数字 a ^ 0 = a; a ^ a = 0 🌟
✅137. 只出现一次的数字 II (a >> i) & 1 取出a的第i位 🌟🌟
✅187. 重复的DNA序列 用二进制表示x = ((x << 2) | bin[ch]) & ((1 << 20) - 1) 🌟🌟
❌✅190. 颠倒二进制位 还有个分治法 🌟
✅191. 位1的个数 n & (n - 1)消除二进制n的最后一位1 🌟
✅201. 数字范围按位与 寻找公共前缀，n&(n-1)消除最后一位1 🌟🌟
✅231. 2 的幂 同191 260 🌟
✅260. 只出现一次的数字 III x的最后一位1：x & -x 🌟🌟
✅268. 丢失的数字 a ^ a = 0 🌟
❌287. 寻找重复数 难以理解 🌟🌟
✅318. 最大单词长度乘积 将字母用掩码表示，取并为0则表示二者没用重复字符 🌟🌟
❌✅338. 比特位计数 x&(x-1)消除1，还有动态规划解法 🌟
✅342. 4的幂 4的幂是2的偶数次幂，且%3=1 🌟
✅371. 两整数之和 python整型无限长，用32位补码表示32位有符号整型，负数最高位全为1 🌟🌟
✅389. 找不同 ord(a), chr(1) 🌟
✅645. 错误的集合 同260 🌟