常见位运算基础
掌握几个核心操作能解决大部分底层问题：
- 判断第 x 位：
(n >> x) & 1 - 置第 x 位为 1：
n |= (1 << x) - 置第 x 位为 0：
n &= ~(1 << x) - Lowbit 提取最右侧 1：
n & -n - 消除最右侧 1：
n & (n - 1)
1. 位 1 的个数
统计无符号整数二进制中 1 的数量。
思路一：逐位移位比较，循环 32 次。思路二：利用 n & (n - 1) 每次消除一个最低位的 1，直到 n 为 0。这种方法效率更高，取决于 1 的个数。
class Solution {
public:
int hammingWeight(uint32_t n) {
int ans = 0;
while (n) {
n &= (n - 1);
ans++;
}
return ans;
}
};
2. 比特位计数
计算 0 到 n 每个数的二进制 1 的个数。
暴力法对每个数调用上述函数，复杂度 O(32n)。动态规划更优：偶数右移后 1 的个数不变，奇数则多 1。公式：dp[i] = dp[i >> 1] + (i & 1)。
class Solution {
public:
vector<int> countBits(int n) {
vector<int> ret(n + 1);
for (int i = 0; i <= n; ++i)
ret[i] = ret[i >> 1] + (i & 1);
return ret;
}
};
3. 汉明距离
两数二进制位不同的位置数。
直接异或 x ^ y，结果中 1 的个数即为答案。利用 lowbit 快速统计即可。
{
:
{
ret = ;
( i = x ^ y; i > ; i -= (i & -i))
ret++;
ret;
}
};
