引言
在算法竞赛和底层开发中，位运算（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;
}五、总结
位运算通过直接操作二进制位，能够实现：
-
高效数学运算（如乘除、取模）；
-
状态压缩（优化DP、集合操作）；
-
算法优化（快速幂、Brian Kernighan算法）。
掌握位运算，不仅能提升代码性能，还能在面试和竞赛中脱颖而出。建议通过LeetCode相关题目（如268、371、201）加强练习。
