常见位运算总结
刷前必刷题单
在深入具体题目之前，先回顾几个经典的位运算技巧，这些是解决后续问题的基础。
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;
}
result;
}
};
