C++ 位运算技巧涵盖基础操作如位移、掩码及 lowbit 等。通过 LeetCode 经典题目解析位运算应用,包括统计二进制中 1 的个数、计算汉明距离、寻找单一数字及其变体、检测字符唯一性、查找丢失数字以及无符号加法实现。重点讲解异或运算性质、动态规划优化比特计数、分治策略处理缺失元素等问题,提供线性时间复杂度且空间高效的解决方案。代码示例基于 C++ 实现,适合算法学习与面试准备。
classSolution {
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;
}
};
动态规划的解法时间复杂度严格为 O(n)。
3. 汉明距离
题目: [461. 汉明距离]
题目描述:
两个整数的 汉明距离 是指这两个数字对应的二进制位不同的位置的个数。
给定两个整数 x 和 y,计算它们之间的汉明距离。
示例 1:
输入:2
输出:2
示例 2:
输入:x = 3, y = 1
输出:1
提示:
0 <= x, y <= 2^31 - 1
解题思路
将输入的 x 和 y 右移,逐位比较,统计对应二进制位不同的位置的数目,当 x | y 为 0 时,说明两个数最高位 1 统计完,结束循环。
代码实现
classSolution {
public:
inthammingDistance(int x, int y){
int ans = 0;
while (x | y) {
int a = x & 1, b = y & 1;
ans += a ^ b;
x >>= 1;
y >>= 1;
}
return ans;
}
};
这道题还可以用 lowbit 来求解,lowbit 可以提取一个数二进制表示最右侧的 1。
我们可以先将 x 和 y 异或起来,再统计异或结果中 1 的个数。
classSolution {
public:
intlowbit(int x){
return x & -x;
}
inthammingDistance(int x, int y){
int ret = 0;
for (int i = x ^ y; i > 0; i -= lowbit(i)) ret++;
return ret;
}
};
4. 只出现一次的数字
题目: [136. 只出现一次的数字]
题目描述:
给定一个整数数组 nums,其中元素出现的次数可以是 2 或 1,请你找出只出现一次的元素。
你必须实现一个线性时间复杂度的算法,并且不使用额外空间。
示例 1:
输入:nums = [2, 2, 1]
输出:1
示例 2:
输入:nums = [4, 1, 2, 1, 2]
输出:4
示例 3:
输入:nums = [1]
输出:1
提示:
1 <= nums.length <= 3 * 10^4
-3 * 10^4 <= nums[i] <= 3 * 10^4
除了某个元素只出现一次以外,其余每个元素均出现两次。
解题思路
对这道题,我们可以使用哈希表来统计数字出现的次数,然后遍历一次哈希表找出出现次数为 1 的数字。
当然这道题更优的解法是使用异或运算,直接将所有的数异或起来就能得到出现次数为 1 的数字。
代码实现
classSolution {
public:
intsingleNumber(vector<int>& nums){
int ret = 0;
for (auto num : nums) ret ^= num;
return ret;
}
};
通过第 i 位上值的不同,将原数组划分,因为异或结果二进制表示位为 1 表示只出现一次的两个数字 a 和 b 该比特位的不同,我们只需要根据这个划分依据分别将对应的数字异或起来就能得到只出现一次的两个数字。
原理:异或运算,相同为 0,不同为 1。
代码实现
classSolution {
public:
vector<int> singleNumber(vector<int>& nums){
int x = 0; // a ^ b = xfor (auto e : nums) x ^= e;
// 判断 x 第几位是 1int i = 0;
for (i = 0; i < 32; ++i)
if ((x >> i) & 1) break;
// 根据第 i 位划分原数组int a = 0, b = 0;
for (auto e : nums) {
if ((e >> i) & 1) a ^= e;
else b ^= e;
}
return {a, b};
}
};
classSolution {
public:
intsingleNumber(vector<int>& nums){
int x = 0;
for (int i = 0; i < 32; ++i) {
int bitSum = 0;
for (auto e : nums) bitSum += (e >> i) & 1;
x |= (bitSum % 3) << i;
}
return x;
}
};
classSolution {
public:
intmissingNumber(vector<int>& nums){
int x = 0;
for (auto e : nums) x ^= e;
for (int i = 0; i <= nums.size(); ++i) x ^= i;
return x;
}
};
高斯求和
classSolution {
public:
intmissingNumber(vector<int>& nums){
int n = nums.size();
// 高斯公式求和int sum = n * (n + 1) / 2;
for (auto e : nums) sum -= e;
return sum;
}
};
哈希
classSolution {
public:
intmissingNumber(vector<int>& nums){
int n = nums.size();
int* hash = newint[n + 1]{0};
for (auto e : nums) hash[e]++;
for (int i = 0; i <= n; ++i) {
if (hash[i] == 0) {
delete[] hash;
return i;
}
}
return-1;
}
};
异或结果二进制表示位为 1 表示缺失的两个数字 a 和 b 该比特位的不同,找出异或值二进制表示最低位的 1 是第 i 位。
通过第 i 位上值的不同,将 [1, n] 和数组 nums 的所有元素划分,我们只需要根据这个划分依据分别将对应的元素异或起来就能得到缺失的两个数字。
代码实现
classSolution {
public:
vector<int> missingTwo(vector<int>& nums){
// 1. 求出缺失两个数的异或 xint n = nums.size(), x = 0;
for (int i = 1; i <= n + 2; ++i) x ^= i;
for (auto e : nums) x ^= e;
// 2. 找出 a b 二进制中不同的那位 diffint diff = 0;
while (((x >> diff) & 1) == 0) diff++;
// 3. 根据 diff 位的不同,将所有的数划分为两类并异或int a = 0, b = 0;
for (auto e : nums)
if ((e >> diff) & 1) a ^= e;
else b ^= e;
for (int j = 1; j <= n + 2; ++j)
if ((j >> diff) & 1) a ^= j;
else b ^= j;
return {a, b};
}
};