位运算核心技巧与实战解析
位运算是算法面试中的高频考点，掌握其底层逻辑能显著提升解题效率。本文将系统梳理位运算的基础操作与进阶技巧，并结合经典算法题进行实战演练。
1. 位运算复习与补充
在 C 语言阶段我们已经接触过移位操作符（<<、>>）、按位与（&）、按位或（|）、按位异或（^）以及按位取反（~）。为了巩固基础，我们先回顾这些操作符的核心逻辑。
基础位运算逻辑
<<和>>：分别实现二进制位的左移和右移。&：按位与，对应位置均为 1 时结果为 1，否则为 0。|：按位或，对应位置均为 0 时结果为 0，否则为 1。^：按位异或，对应位置不同为 1，相同为 0。~：按位取反，0 变 1，1 变 0。简单记忆口诀：& 有 0 则 0，| 有 1 则 1，^ 相同为 0 相异为 1。
常用位操作技巧
1. 判定二进制第 x 位是 0 还是 1
判断数字 n 的二进制第 x 位是否为 1，可以通过右移 x 位后与 1 进行按位与运算：
(n >> x) & 1
若结果为 1 表示该位为 1，否则为 0。
2. 将第 x 位修改为 1
利用按位或的特性，只要某一位与 1 进行或运算，结果必为 1：
n |= (1 << x)
3. 将第 x 位修改为 0
利用按位与的特性，某一位与 0 进行与运算，结果必为 0。需先构造一个掩码，将第 x 位变为 0，其余位为 1：
n &= ~(1 << x)
4. 提取最右侧的 1
利用补码特性，n & -n 可以提取出二进制表示中最右侧的 1。例如 n = 6 (110)，-n = ...010，两者按位与得到 2 (010)。
5. 去掉最右侧的 1
n & (n - 1) 可以将最右侧的 1 变为 0。这是统计二进制中 1 的个数的关键技巧。
6. 位图思想
当需要存储大量数据的存在性（0 或 1）时，使用整型数组占用空间较大。位图利用每个二进制位代表一个状态，一个 32 位整数可表示 32 个元素的存在情况，大幅节省内存。
7. 异或运算律
a ^ 0 = aa ^ a = 0a ^ b ^ c = a ^ (b ^ c)（满足结合律）
2. 位运算算法题实战
2.1 位 1 的个数
题目：计算给定正整数二进制表示中 1 的个数。
思路：利用 n & (n - 1) 每次消除最右侧的 1，循环直到 n 为 0，统计次数即可。
class Solution {
public:
int hammingWeight(int n) {
int count = 0;
while (n != 0) {
n &= (n - 1);
count++;
}
return count;
}
};
2.2 比特位计数
题目：返回从 0 到 n 每个数字二进制中 1 的个数。
思路：对每个数单独调用上述方法统计，或者利用动态规划优化，但基础解法已足够直观。
class Solution {
public:
vector<int> countBits(int n) {
vector<int> ret(n + 1);
for (int i = 0; i <= n; i++) {
int count = 0, tmp = i;
while (tmp > 0) {
tmp &= (tmp - 1);
count++;
}
ret[i] = count;
}
return ret;
}
};
2.3 汉明距离
题目：计算两个整数二进制表示中不同位的个数。
思路：先异或 x ^ y，不同位即为 1，再统计结果中 1 的个数。
class Solution {
public:
int hammingDistance(int x, int y) {
int ret = x ^ y, count = 0;
while (ret > 0) {
ret &= (ret - 1);
count++;
}
return count;
}
};
2.4 只出现一次的数字
题目：数组中除一个数字外，其他都出现两次，找出那个唯一的数。
思路：利用 a ^ a = 0 和 a ^ 0 = a，全部元素异或即可抵消成对的数字。
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ret = 0;
for (auto x : nums) {
ret ^= x;
}
return ret;
}
};
2.5 只出现一次的数字 III
题目：数组中有两个数字只出现一次，其余出现两次，找出这两个数。
思路：所有数异或得到 t = a ^ b。找到 t 中任意为 1 的位（如最右侧 1），根据该位将数组分为两组，分别异或即可得到两个数。
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
unsigned int t = 0;
for (auto x : nums) t ^= x;
int t1 = 0, t2 = 0;
// 获取最右侧的 1
int c = t & (-t);
for (auto x : nums) {
if ((x & c) == 0) t1 ^= x;
else t2 ^= x;
}
return {t1, t2};
}
};
3. 进阶练习题
3.1 判断字符是否唯一
题目：判断字符串中是否包含重复字符。
思路：小写字母共 26 个，可用一个整型变量作为位图。遍历字符串，检查对应位是否已置 1。注意鸽巢原理，长度大于 26 直接返回 false。
class Solution {
public:
bool isUnique(string astr) {
if (astr.size() > 26) return false;
int t = 0;
for (auto x : astr) {
int cur = int(x - 'a');
if ((t >> cur) & 1) return false;
t |= (1 << cur);
}
return true;
}
};
3.2 丢失的数字
题目：找出 [0, n] 范围内缺失的一个数字。
思路：
- 位运算法：将
0到n全部异或，再与数组元素异或，成对出现的会抵消，剩下缺失的数。 - 高斯求和：计算
0到n的和，减去数组元素总和。
class Solution {
public:
int missingNumber(vector<int>& nums) {
int n = nums.size();
int ret = 0;
// 异或法
for (int i = 0; i <= n; i++) ret ^= i;
for (auto x : nums) ret ^= x;
return ret;
}
};
3.3 两整数之和
题目：不使用 + 和 - 计算两数之和。
思路：
- 无进位和：
a ^ b - 进位：
(a & b) << 1 - 递归或循环直到进位为 0。
class Solution {
public:
int getSum(int a, int b) {
while (b) {
int x = a ^ b;
unsigned int y = (unsigned int)((a & b) << 1);
a = x, b = y;
}
return a;
}
};
3.4 只出现一次的数字 II
题目：除一个数字外，其他都出现三次，找出那个唯一的数。
思路：统计每一位上 1 出现的总次数，对 3 取模，余数为 1 则该位属于目标数字。
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ret = 0;
for (int i = 0; i < 32; i++) {
int sum = 0;
for (auto x : nums) {
if ((x >> i) & 1) sum++;
}
if (sum % 3) ret |= (1 << i);
}
return ret;
}
};
3.5 消失的两个数字
题目：找出 [1, n] 中缺失的两个数字。
思路：类似'只出现一次的数字 III'，先对所有数字（包括缺失的）与数组元素异或，得到两个缺失数的异或值，再分组求解。
class Solution {
public:
vector<int> missingTwo(vector<int>& nums) {
unsigned int s = 0;
int n = nums.size() + 2;
for (int i = 1; i <= n; i++) s ^= i;
for (auto x : nums) s ^= x;
int t = s & (-s);
int ret1 = 0, ret2 = 0;
for (auto x : nums) {
if (x & t) ret1 ^= x;
else ret2 ^= x;
}
for (int i = 1; i <= n; i++) {
if (i & t) ret1 ^= i;
else ret2 ^= i;
}
return {ret1, ret2};
}
};
通过上述练习，希望能帮助大家建立位运算的思维模型。在实际编码中，灵活运用这些技巧往往能让代码更简洁高效。
