前置知识储备
掌握基础位操作符是理解后续算法的前提。
经典题目实战
判定字符是否唯一
思路分析： 利用【位图】的思想，每一个【比特位】代表一个【字符】。一个 int 类型的变量有 32 位，足够表示所有的小写字母。若某一位为 0，表示该字符未出现；若为 1，则表示已出现。 这里可以用一个整数直接充当哈希表。
class Solution {
public:
bool isUnique(string astr) {
// 利用鸽巢原理优化，小写字母最多 26 个
if(astr.size() > 26) return false;
int bitmap = 0;
for(auto i : astr){
int e = i - 'a';
// 先判断字符是否出现过
if(((bitmap >> e) & 1) == 1) return false;
// 把当前字符加入到位图中
bitmap |= 1 << e;
}
return true;
}
};
消失的数字
思路分析： 设数组大小为 n，原序列应为 [0, n]，现缺失一个数。如果我们将数组中的所有数，以及 [0, n] 范围内的所有数全部【异或】在一起，根据异或的自反性（消消乐规则），成对出现的数字会抵消，最终剩下的就是缺失的那个数字。
class Solution {
public:
int missingNumber(vector<int>& nums) {
int ret = 0;
// 与数组中所有元素异或
for(auto i : nums) ret ^= i;
// 再与 0 到 n 的所有数异或
for(int i = 0; i <= nums.size(); i++) ret ^= i;
return ret;
}
};
两整数之和
思路分析：
● 异或 ^ 运算本质是【无进位加法】；
● 按位与 & 操作能够得到【进位】；
● 将无进位结果与进位左移后的结果相加，循环直到进位为 0。
注意处理负数时的符号位问题，进位计算需使用无符号类型避免移位溢出。
class Solution {
public:
int getSum(int a, int b) {
while(b){
int x = a ^ b; // 无进位相加的结果
unsigned int carry = (unsigned int)(a & b) << 1; // 进位，转为无符号防止溢出
a = x;
b = carry;
}
return a;
}
};
只出现一次的数字 II
思路分析：
数组中只有一个数出现一次，其余都出现三次。我们可以统计每一位上 1 出现的总次数。对于目标数 ret 的某一位，如果该位在数组所有数的对应位上总和模 3 余 1，则说明 ret 的这一位是 1，否则为 0。通过遍历 32 位即可还原出 ret。
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ret = 0;
for(int i = 0; i < 32; i++){ // 依次检查每一位
int sum = 0;
for(auto x : nums)
if(x & (1 << i)) sum++;
sum %= 3;
if(sum & 1) ret |= 1 << i;
}
return ret;
}
};
只出现一次的数字 III
思路分析：
- 将所有数异或在一起，结果为两个只出现一次的数
a和b的异或值tmp = a ^ b。 a不等于b，所以tmp至少有一位为 1。找到这一位，它代表了a和b在该位上的二进制不同。- 根据这一位将数组分为两类，分别异或，即可得到
a和b。
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
int tmp = 0;
for(auto x : nums) tmp ^= x;
// 找出 a, b 中比特位不同的那一位
int diff = 0;
while(1){
if(((tmp >> diff) & 1) == 1) break;
else diff++;
}
// 根据 diff 位的不同，将所有数划分成两类分别异或
int a = 0, b = 0;
for(auto x : nums){
if((x >> diff) & 1) b ^= x;
else a ^= x;
}
return {a, b};
}
};
消失的两个数字
思路分析： 本题结合了'消失的数字'和'只出现一次的数字 III'。先将数组中的数和 [1, n+2] 区间内的所有数【异或】在一起，问题就转化为：有两个数出现了一次，其余出现了两次。这便回到了上一题的解法。
class Solution {
public:
vector<int> missingTwo(vector<int>& nums) {
int tmp = 0;
for(auto x : nums) tmp ^= x;
for(int i = 1; i <= nums.size() + 2; i++) tmp ^= i;
// 找出 a, b 中比特位不同的那一位
int diff = 0;
while(1){
if(((tmp >> diff) & 1) == 1) break;
else diff++;
}
// 分组异或
int a = 0, b = 0;
for(auto 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};
}
};
