c++常见位运算

位运算在算法竞赛中非常常见，因为它们可以高效地处理二进制数据，常用于状态压缩、优化计算、快速判断等场景。以下是一些常见的位运算技巧和应用：

1. 基本位运算操作

1.1 按位与（&）

• 功能：两个二进制数的对应位都为 1 时，结果的对应位为 1，否则为 0。
• 示例：

  int a = 5;    // 0101
  int b = 3;    // 0011
  int c = a & b; // 0001 (1)
  

1.2 按位或（|）

• 功能：两个二进制数的对应位有一个为 1 时，结果的对应位为 1，否则为 0。
• 示例：

  int a = 5;    // 0101
  int b = 3;    // 0011
  int c = a | b; // 0111 (7)
  

1.3 按位异或（^）

• 功能：两个二进制数的对应位不同时，结果的对应位为 1，否则为 0。
• 示例：

  int a = 5;    // 0101
  int b = 3;    // 0011
  int c = a ^ b; // 0110 (6)
  

1.4 按位取反（~）

• 功能：将二进制数的每一位取反（0 变 1，1 变 0）。
• 示例：

  int a = 5;    // 0101
  int b = ~a;   // 1010 (补码表示，实际值为 -6)
  

1.5 左移（<<）

• 功能：将二进制数的所有位向左移动，低位补 0。
• 示例：

  int a = 5;    // 0101
  int b = a << 1; // 1010 (10)
  

1.6 右移（>>）

• 功能：将二进制数的所有位向右移动，高位补 0（无符号数）或补符号位（有符号数）。
• 示例：

  int a = 5;    // 0101
  int b = a >> 1; // 0010 (2)
  

2. 常见位运算技巧

2.1 判断奇偶性

• 方法：使用 & 操作判断最低位是否为 1。
• 示例：

  bool isOdd(int n) {
      return n & 1;
  }
  

2.2 交换两个数

• 方法：使用异或操作交换两个数，无需额外空间。
• 示例：

  void swap(int& a, int& b) {
      a ^= b;
      b ^= a;
      a ^= b;
  }
  

2.3 取最低位的 1

• 方法：使用 n & -n。
• 示例：

  int lowbit(int n) {
      return n & -n;
  }
  

2.4 判断是否为 2 的幂

• 方法：如果 n & (n - 1) == 0，则 n 是 2 的幂。
• 示例：

  bool isPowerOfTwo(int n) {
      return n > 0 && (n & (n - 1)) == 0;
  }
  

2.5 统计二进制中 1 的个数

• 方法：使用 n & (n - 1) 不断消除最低位的 1。
• 示例：

  int countOnes(int n) {
      int count = 0;
      while (n) {
          n &= (n - 1);
          count++;
      }
      return count;
  }
  

2.6 快速乘/除 2

• 方法：左移 1 位相当于乘 2，右移 1 位相当于除 2。
• 示例：

  int multiplyByTwo(int n) {
      return n << 1;
  }
  
  int divideByTwo(int n) {
      return n >> 1;
  }
  

3. 位运算的应用场景

3.1 状态压缩

• 描述：将多个状态压缩到一个整数中，常用于动态规划、回溯等算法。
• 示例：

  int mask = 0; // 初始状态
  mask |= (1 << 2); // 设置第 2 位为 1
  mask |= (1 << 4); // 设置第 4 位为 1
  bool isSet = (mask & (1 << 2)) != 0; // 检查第 2 位是否为 1
  

3.2 子集枚举

• 描述：枚举一个集合的所有子集。
• 示例：

  int n = 3; // 集合大小为 3
  for (int mask = 0; mask < (1 << n); mask++) {
      for (int i = 0; i < n; i++) {
          if (mask & (1 << i)) {
              // 第 i 个元素在子集中
          }
      }
  }
  

3.3 快速幂

• 描述：利用位运算快速计算幂次。
• 示例：

  int fastPow(int base, int exponent) {
      int result = 1;
      while (exponent > 0) {
          if (exponent & 1) {
              result *= base;
          }
          base *= base;
          exponent >>= 1;
      }
      return result;
  }
  

3.4 掩码操作

• 描述：使用掩码提取或设置特定位。
• 示例：

  int n = 0b101010; // 42
  int mask = 0b1111; // 15
  int lowerBits = n & mask; // 提取低 4 位
  

4. 位运算的注意事项

• 优先级：位运算的优先级较低，建议使用括号明确运算顺序。
• 符号位：右移操作对有符号数和无符号数的处理方式不同。
• 溢出：左移操作可能导致溢出，需注意数据范围。