基础笔记 -- 位运算

br

前言

​ ​ 位运算是直接对整数的二进制位进行操作的运算，它在计算机编程中有着广泛的应用。以下是位运算的详细介绍：

1. 位运算符及其功能

按位与（&）

• 规则：两个对应位都为1时，结果位为1，否则为0。
• 示例：
  • 5 & 3：

      0101  (5的二进制)
    & 0011  (3的二进制)
    ------
      0001  (结果为1)
    

• 应用：
  • 判断奇偶性：n & 1，结果为1表示奇数，为0表示偶数。
  • 提取特定位：与掩码进行按位与运算，可提取指定位的信息。

按位或（|）

• 规则：两个对应位中有一个为1时，结果位为1。
• 示例：
  • 5 | 3：

      0101
    | 0011
    ------
      0111  (结果为7)
    

• 应用：
  • 设置特定位为1：n | 0x01，将最低位设置为1。

按位异或（^）

• 规则：两个对应位不同时，结果位为1，相同时为0。
• 示例：
  • 5 ^ 3：

      0101
    ^ 0011
    ------
      0110  (结果为6)
    

• 应用：
  • 交换两个数（无需临时变量）：

    a = a ^ b
    b = a ^ b
    a = a ^ b
    

  • 检测两个数是否相等：a ^ b == 0表示相等。

按位取反（~）

• 规则：将每一位取反，0变为1，1变为0。
• 示例：
  • ~5：

      0000 0101  (5的补码)
    ~
    ------
      1111 1010  (取反结果，表示-6的补码)
    

• 注意：在补码表示中，~x等价于 -(x+1)。

左移（<<）

• 规则：将二进制位向左移动指定位数，右侧补0。
• 示例：
  • 5 << 2：

      0101  (5的二进制)
    << 2
    ------
      10100  (结果为20)
    

• 应用：乘以2的幂次：n << k等价于 n * (2^k)。

右移（>>）

• 规则：将二进制位向右移动指定位数，左侧根据符号位填充（正数补0，负数补1）。
• 示例：
  • 20 >> 2：

      10100  (20的二进制)
    >> 2
    ------
      0101  (结果为5)
    

• 应用：除以2的幂次：n >> k等价于 n // (2^k)。

2. 位运算的应用场景

优化性能

• 位运算速度快，可用于优化算法，例如：

  • 快速判断奇偶性。（num & 1 == 1 → 奇数；num & 1 == 0 → 偶数）
  • 位向量（BitVector）用于高效存储和查询大量布尔值。

数据处理

• 位掩码操作：
  • 使用掩码提取、设置或清除特定位。
• 压缩数据：
  • 利用位运算将多个数据压缩到一个整数中，节省存储空间。

算法设计

• 状态压缩：
  • 在动态规划等算法中，用位表示状态，提高空间效率。
• 位运算技巧：
  • 统计二进制中1的个数。
  • 交换两个数无需临时变量。

3. 注意事项

• 数据类型：
  • 位运算通常用于整数类型，不适用于浮点数。
• 符号位处理：
  • 右移运算时，负数可能因符号位填充导致结果不符合预期。
• 可读性：
  • 过度使用位运算可能降低代码可读性，应适度使用并添加注释。

总结

​ ​ 位运算是直接操作二进制位的强大工具，能够提升程序性能，优化算法，实现高效的数据处理。掌握位运算的基本原理和常用技巧，对于编写高效、紧凑的代码具有重要意义。