常见位运算总结
前置知识：常用位运算技巧
在深入具体题目之前，先回顾几个高频使用的位运算技巧，它们往往是解题的关键。
1. 清除最右侧的 1
n & (n - 1) 可以将整数 n 二进制表示中最右侧的 1 变为 0。这个操作常用于统计二进制中 1 的个数（汉明重量）。
class Solution {
public:
int hammingWeight(int n) {
int count = 0;
while (n) {
n &= (n - 1);
count++;
}
return count;
}
};
2. 异或运算的性质
- 任何数与自身异或结果为
0(a ^ a = 0)。 - 任何数与
0异或结果为其本身 (a ^ 0 = a)。 - 异或满足交换律和结合律。
利用这些性质，可以解决'只出现一次的数字'类问题。
class Solution {
public:
int singleNumber(vector<int>& nums) {
int result = 0;
for (int num : nums) {
result ^= num;
}
return result;
}
};
033 判断字符是否唯一
题目描述： 实现一个算法，确定一个字符串的所有字符是否全都不同。这里假设字符串只包含小写字母。
解法思路：位图思想
由于题目限制只包含小写字母，总共只有 26 个字符。我们可以用一个整数的二进制位来代表一个字符是否存在。一个 int 类型有 32 位，足以覆盖所有小写字母。
- 如果某一位是
0，表示该字符未出现过。 - 如果某一位是
1，表示该字符已出现过。
此外，利用鸽巢原理，如果字符串长度超过 26，必然存在重复字符，可直接返回 false。
算法实现
class Solution {
public:
bool isUnique(string astr) {
// 利用鸽巢原理做优化
if (astr.size() > 26) return false;
int bitMap = 0;
for (char ch : astr) {
int i = ch - 'a';
// 检查第 i 位是否已经是 1
if ((bitMap >> i) & 1) return false;
// 将第 i 位设为 1
bitMap |= (1 << i);
}
return true;
}
};
关键点
实际编码时，注意位移操作的优先级。(bitMap >> i) & 1 用于读取特定位，bitMap |= (1 << i) 用于设置特定位。推导过程中建议自己在纸上画出二进制变化过程，这有助于理解位图映射的本质。
034 丢失的数字
题目描述：
给定一个包含 [0, n] 中 n 个数的数组，找出其中没有出现的那个数。
解法思路：异或消去
数组长度为 n，原本应该包含 0 到 n 共 n+1 个数。现在少了一个。
如果我们把数组中的所有元素，以及 0 到 n 的所有数字全部进行异或运算，根据异或的特性（相同为 0），成对出现的数字都会抵消为 0，最终剩下的就是那个缺失的数字。
算法实现
class Solution {
public:
int missingNumber(vector<int>& nums) {
int ret = 0;
// 异或数组中的元素
for (int x : nums) ret ^= x;
// 异或 0 到 n 的所有数字
for (int i = 0; i <= nums.size(); i++) ret ^= i;
return ret;
}
};
关键点
这种方法空间复杂度为 O(1)，时间复杂度为 O(n)。不需要额外的哈希表或排序，非常高效。核心在于理解'成对抵消'的逻辑。
035 两整数之和
题目描述：
不使用运算符 + 和 -，计算两个整数 a 和 b 的和。
解法思路：模拟加法器
计算机底层加法是通过逻辑门电路实现的，可以分为两步：
- 无进位相加：使用异或
^运算。1 ^ 1 = 0,0 ^ 0 = 0,1 ^ 0 = 1。 - 计算进位：使用按位与
&运算并左移一位。1 & 1 = 1，进位发生在高位。
循环执行这两个步骤，直到进位为 0，此时 a 即为最终结果。
算法实现
class Solution {
public:
int getSum(int a, int b) {
while (b != 0) {
int x = a ^ b; // 无进位和
unsigned int carry = (unsigned int)(a & b) << 1; // 进位
a = x;
b = carry;
}
return a;
}
};
关键点
注意进位计算时使用了 unsigned int 强制转换。因为如果 a & b 的结果是负数（最高位为 1），直接左移可能导致未定义行为。转换为无符号数后左移是安全的。虽然面试中可以直接写 return a + b;，但掌握底层原理对理解计算机组成至关重要。
036 只出现一次的数字 II
题目描述： 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
解法思路：比特位计数
既然其他数字都出现了三次，那么对于任意一个比特位，如果我们将所有数字在该位上的值加起来，总和应该是 3 的倍数加上目标数字在该位的值（0 或 1）。
因此，遍历 32 个比特位，统计每一位上 1 出现的次数。如果次数模 3 余 1，说明目标数字在该位上是 1；否则是 0。
算法实现
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ret = 0;
for (int i = 0; i < 32; i++) {
int sum = 0;
for (int x : nums) {
if (((x >> i) & 1) == 1) sum++;
}
if (sum % 3 == 1) {
ret |= (1 << i);
}
}
return ret;
}
};
关键点
此方法适用于'出现 K 次找 1 次'的通用场景。虽然代码嵌套了两层循环，但外层固定为 32，整体时间复杂度仍视为 O(n)。处理负数时需注意补码表示，上述逻辑对补码同样有效。
037 消失的两个数字
题目描述：
给定一个包含 0 到 n 中 n 个数的数组，其中有两个数字消失了，找出这两个数字。
解法思路：组合拳
这道题其实是前面两道题的结合版：
- 类似于'丢失的数字'，先将数组中的数和
1到n+2区间内的所有数异或在一起。这样得到的结果是两个缺失数字的异或值（记为tmp）。 - 类似于'只出现一次的数字 III'，我们需要找到区分这两个缺失数字的某一位。
tmp中为1的位，说明这两个缺失数字在这一位上不同。 - 根据这一位将原数组和完整序列分为两组，分别异或，即可得到两个缺失数字。
算法实现
class Solution {
public:
vector<int> missingTwo(vector<int>& nums) {
int tmp = 0;
// 1. 异或所有数字
for (int x : nums) tmp ^= x;
for (int i = 1; i <= nums.size() + 2; i++) tmp ^= i;
// 2. 找到 tmp 中为 1 的最低位（区分位）
int diff = 0;
while (!((tmp >> diff) & 1)) diff++;
// 3. 分组异或
int a = 0, b = 0;
for (int x : nums) {
if ((x >> diff) & 1) b ^= x;
else a ^= x;
}
for (int i = 1; i <= nums.size() + 2; i++) {
if ((i >> diff) & 1) b ^= i;
else a ^= i;
}
return {a, b};
}
};
关键点
关键在于找到区分位 diff。只要找到任意一个不同的比特位，就能将两个目标数分到不同的组里，从而通过异或消除其他干扰项。这种分治思想在位运算题目中非常经典。
结语
位运算不仅是面试中的高频考点，更是理解计算机底层数据处理的基石。掌握这些技巧，不仅能写出更高效的代码，还能在面对复杂问题时找到意想不到的突破口。建议在练习时多尝试自己推导二进制变化过程，加深理解。
