常见位运算总结
刷前必刷题单
在深入具体题目之前，先回顾几个经典的位运算技巧，这些是解决后续问题的基础。
1. 清除最右侧的 1
利用 n & (n - 1) 可以快速将整数二进制表示中最右侧的 1 变为 0。这在统计 1 的个数时非常高效。
class Solution {
public:
int hammingWeight(int n) {
int count = 0;
while (n) {
n &= (n - 1);
count++;
}
return count;
}
};
2. 汉明距离与异或 两个数异或后，结果为 1 的位数即为它们的汉明距离。结合上述技巧可快速计算。
class Solution {
public:
int hammingDistance(int x, int y) {
int val = x ^ y;
int count = 0;
while (val) {
val &= (val - 1);
count++;
}
return count;
}
};
3. 只出现一次的数字
利用异或运算的自反性（a ^ a = 0, a ^ 0 = a），数组中成对出现的数字异或后会抵消，剩下的就是目标值。
class Solution {
public:
int singleNumber(vector<int>& nums) {
int result = 0;
for (int num : nums) {
result ^= num;
}
return result;
}
};
核心要点
做题时不要死记硬背代码，重点在于理解位操作背后的逻辑。建议自己在纸上推导一遍二进制变化过程，这样遇到变体题也能举一反三。
033 判断字符是否唯一
题目描述： 给定一个字符串，判断其中是否包含重复字符。要求不使用额外的数据结构。
解法一：位图思想
既然输入只包含小写字母，我们可以用一个整数的 32 个比特位来代表 26 个字母的状态。如果某一位为 1，说明对应字符已出现过；若再次遇到该字符，则返回 false。
这里有个细节，如果字符串长度超过 26，根据鸽巢原理必然存在重复，可以直接提前返回。
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;
}
};
思路补充
这种用整数代替哈希表的方法在空间受限且数据范围明确时非常有效。注意位移操作的优先级，括号不能少。
034 丢失的数字
题目描述：
给定包含 0 到 n 中 n 个不同整数的数组，找出其中缺失的那个数。
解法：异或消去
数组原本应包含 0 到 n 的所有整数，现在缺了一个。如果我们把数组中的所有元素与 0 到 n 的所有数字进行异或，成对的数字会相互抵消（x ^ x = 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(n)，空间复杂度 O(1)。关键在于理解异或的交换律和结合律。
035 两整数之和
题目描述：
不使用运算符 + 和 -，计算两个整数 a 和 b 的和。
解法：模拟加法器
计算机底层加法分为两步：无进位相加和计算进位。
- 无进位和：通过异或
^实现。 - 进位：通过与
&并左移<< 1实现。
循环执行这两步，直到进位为 0，此时结果即为最终和。
class Solution {
public:
int getSum(int a, int b) {
while (b != 0) {
// 无进位相加
int sum = a ^ b;
// 计算进位，需转为 unsigned 防止负数左移未定义行为
unsigned int carry = (unsigned int)(a & b) << 1;
a = sum;
b = carry;
}
return a;
}
};
思路补充
实际面试中如果遇到此类限制，通常考察的是对底层原理的理解。虽然直接写 return a + b 能通过测试，但无法体现技术深度。注意处理负数时的符号位扩展问题，使用 unsigned int 转换是一种安全的处理方式。
036 只出现一次的数字 II
题目描述： 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
解法：比特位计数
既然其他数字都出现了三次，那么对于任意一个比特位，所有数字在该位上的 1 的总数应该是 3 的倍数。如果加上目标数字后，某一位的 1 的总数不是 3 的倍数，说明目标数字在该位上是 1。
我们遍历 32 个比特位，统计每一位上 1 出现的次数，对 3 取余，即可还原出目标数字。
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) sum++;
}
if (sum % 3 == 1) {
ret |= (1 << i);
}
}
return ret;
}
};
思路补充
这个方法比状态机解法更直观，容易理解。虽然时间复杂度是 O(32n)，但在固定整数位宽下等同于 O(n)。注意处理负数时，C++ 中右移是算术移位，可能会保留符号位，但这里我们逐位构建结果，逻辑依然成立。
037 消失的两个数字
题目描述：
给定一个包含 0 到 n 中 n 个不同整数的数组，其中有两个数字消失了，找出这两个数字。
解法：组合策略
这道题可以看作是'丢失的数字'和'只出现一次的数字 III'的结合。
- 整体异或：将数组所有元素与
1到n+2的所有数字异或。结果将是两个缺失数字的异或值（a ^ b）。 - 区分位：找到
a ^ b结果中任意一个为 1 的位，这意味着a和b在这一位上不同。 - 分组异或：根据这一位将原数组和完整序列分成两组，分别异或。每组的结果即为一个缺失数字。
class Solution {
public:
vector<int> missingTwo(vector<int>& nums) {
int tmp = 0;
// 异或数组元素
for (int x : nums) tmp ^= x;
// 异或 1 到 N
for (int i = 1; i <= nums.size() + 2; i++) tmp ^= i;
// 找到不同的那一位
int diff = 0;
while (!((tmp >> diff) & 1)) diff++;
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};
}
};
思路补充
核心在于利用异或的性质将大问题拆解。找到区分位是关键步骤，它保证了两个缺失数字会被分到不同的组，从而在各自的组内成为唯一的'落单者'。
