常见位运算总结
刷前必刷题单
在深入具体题目之前，先回顾几个经典的位运算技巧。
1. 清除最右侧的 1
利用 n & (n - 1) 可以消除整数二进制表示中最右侧的 1。这在计算汉明重量时非常有用。
class Solution {
public:
int hammingWeight(int n) {
int count = 0;
while (n) {
n &= (n - 1);
count++;
}
return count;
}
};
2. 比特位计数
可以通过动态规划或汉明重量问题来求解。这里展示一种基于汉明重量的解法。
class Solution {
public:
vector<int> countBits(int n) {
vector<int> ans(n + 1);
for (int i = 1; i < n + 1; i++) {
int count = 0;
int nums = i;
while (nums) {
nums &= (nums - 1);
count++;
}
ans[i] = count;
}
return ans;
}
};
3. 异或运算律相关
异或（^）具有交换律和结合律，且 a ^ a = 0。这一性质常用于寻找只出现一次的数字。
class Solution {
:
{
result = ;
( x : nums) {
result ^= x;
}
result;
}
};
