C++位运算精要：高效解题的利器

引言

在算法竞赛和底层开发中，位运算（Bit Manipulation）因其极高的执行效率而广受青睐。它能在O(1)时间复杂度内完成某些复杂操作，大幅优化程序性能。本文系统梳理C++位运算的核心技巧，涵盖基础操作、经典应用、优化策略及实战例题，帮助读者掌握这一高效工具。

---

一、位运算基础

1. 六大基本操作

运算符	名称	示例（二进制）	说明
&	按位与	1010 & 1100 = 1000	同1为1，否则为0
|	按位或	1010|1100 = 1110	有1则1，全0为0
^	按位异或	1010 ^ 1100 = 0110	不同为1，相同为0
~	按位取反	~1010 = 0101（4位）	0变1，1变0
<<	左移	0011 << 2 = 1100	低位补0，相当于×2ⁿ
>>	右移	1100 >> 2 = 0011	高位补符号位（算术右移）

2. 常用位运算性质

• 异或（XOR）特性：

  • a ^ a = 0，a ^ 0 = a

  • 交换律：a ^ b = b ^ a

  • 结合律：(a ^ b) ^ c = a ^ (b ^ c)

• 与（AND）和或（OR）的分配律：

  • a & (b | c) = (a & b) | (a & c)

  • a | (b & c) = (a | b) & (a | c)

---

二、位运算实战技巧

1. 判断奇偶

bool isOdd(int n) {return n & 1; // 奇数返回true
}

原理：二进制末位为1表示奇数。

2. 交换两个数（无需临时变量）

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

注意：若a和b指向同一内存，此方法会失效。

3. 取绝对值

int abs(int n) {int mask = n >> (sizeof(int) * 8 - 1); // 符号位扩展return (n ^ mask) - mask;
}

适用场景：嵌入式设备等无分支优化需求。

4. 检查是否为2的幂

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

原理：2ⁿ的二进制形式为100...0，n & (n-1)会消除唯一的1。

5. 统计二进制中1的个数（Brian Kernighan算法）

int countOnes(int n) {int count = 0;while (n) {n &= (n - 1); // 每次消除最右边的1count++;}return count;
}

时间复杂度：O(k)，k为1的个数。

6. 最低位的1

int lowBit(int x) {return x & (-x);
}

应用：树状数组（Fenwick Tree）的核心操作。

7. 模拟集合操作

• 表示集合：用整数二进制位表示元素是否存在（如mask = 5（101）表示包含第0和第2个元素）。

• 常用操作：

  int S = 0b1010;          // 集合{1, 3}
  S |= (1 << 2);           // 添加元素2 → S = 0b1110
  S &= ~(1 << 1);          // 删除元素1 → S = 0b1100
  bool has = S & (1 << 3); // 检查元素3是否存在

---

三、位运算优化策略

1. 替代乘除法

• 左移1位等价于×2：

  int a = 5;
  a <<= 1; // a = 10

• 右移1位等价于÷2（向下取整）：

  int b = 7;
  b >>= 1; // b = 3

2. 状态压缩DP

问题示例：旅行商问题（TSP）中，用二进制数表示访问过的城市。

int dp[1 << n][n]; // dp[mask][i]表示从城市i出发，访问过mask集合的最短路径
for (int mask = 0; mask < (1 << n); mask++) {for (int i = 0; i < n; i++) {if (mask & (1 << i)) {// 状态转移}}
}

3. 快速幂算法

int fastPow(int a, int b) {int res = 1;while (b) {if (b & 1) res *= a;a *= a;b >>= 1;}return res;
}

时间复杂度：O(log b)。

---

四、经典例题解析

例题1：只出现一次的数字（LeetCode 136）

问题：数组中只有一个数出现一次，其余均出现两次，找出该数。
解法：

int singleNumber(vector<int>& nums) {int res = 0;for (int num : nums) res ^= num;return res;
}

关键点：利用a ^ a = 0的性质。

例题2：位1的个数（LeetCode 191）

问题：统计无符号整数的二进制表示中1的个数。
解法：

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

例题3：子集生成（LeetCode 78）

问题：给定无重复元素的数组，返回所有子集。
位运算解法：

vector<vector<int>> subsets(vector<int>& nums) {int n = nums.size();vector<vector<int>> res;for (int mask = 0; mask < (1 << n); mask++) {vector<int> subset;for (int i = 0; i < n; i++) {if (mask & (1 << i)) subset.push_back(nums[i]);}res.push_back(subset);}return res;
}

---

五、总结

位运算通过直接操作二进制位，能够实现：

1. 高效数学运算（如乘除、取模）；

2. 状态压缩（优化DP、集合操作）；

3. 算法优化（快速幂、Brian Kernighan算法）。

掌握位运算，不仅能提升代码性能，还能在面试和竞赛中脱颖而出。建议通过LeetCode相关题目（如268、371、201）加强练习。