位运算算法：解锁高效编程的钥匙
常见位运算场景：
5.消失的两个数字
1.判定字符是否唯一
解法一：使用HashSet
借助 HashSet 存储字符。HashSet 不允许有重复元素，在遍历字符串时尝试添加字符，若添加失败就表明有重复字符，返回 false；若遍历完都没出现添加失败的情况，则返回 true
class Solution {
public boolean isUnique(String astr) {
//大优化
if(astr.length() > 26) return false;//因为只包含小写字母
Set<Character> set = new HashSet<>();
// 创建一个 HashSet 来存储字符
char[] s = astr.toCharArray();
for(char c:s){
if(!set.add(c)) return false;// 如果添加失败，说明字符已经存在于集合中
}
return true;
}
} 
解法二：使用位图
我们从位图可以表示是否出现过
class Solution {
public boolean isUnique(String astr) {
int bitmap = 0;
if(astr.length() > 26) return false;//进行优化
for(int i = 0;i<astr.length();i++){
int x = astr.charAt(i) - 'a';
if(((bitmap>>x) & 1) == 1) return false;//使用了检查x位置是否为1
bitmap = 1<<x | bitmap;//使用了将x位置修改成1
}
return true;
}
} 
2.丢失的数字
解法一：使用Set容器（时间复杂度 O(n）,空间复杂度O(n）)
创建一个 HashSet 对象 set，用于存储数组中的元素，遍历数组 nums，将每个元素添加到 set 中，遍历从 0 到 n 的所有数字，检查 set 中是否包含该数字。如果不包含，则返回该数字。
class Solution {
public int missingNumber(int[] nums) {
//1.使用哈希表
int n = nums.length;//定义长度
Set<Integer> set = new HashSet<>();//定义一个Set容器
for(int num:nums){
set.add(num);
}//遍历存放
//找出那个没有存放元素的下标并返回
for(int i = 0;i <= n ;i++){
if(!set.contains(i)) return i;
}
return -1;
}
}
解法二：高斯求和(时间复杂度O(1) )
解题思路：我们可以先根据数组长度 n 计算出从 0 到 n 的所有数字的总和，然后计算数组中所有元素的和，两者相减就能得到缺失的数字。
class Solution {
public int missingNumber(int[] nums) {
//高斯求和
int n = nums.length;
int totalSum = n * (n + 1) / 2;//区间所有元素和
int numsSum = 0;
for(int x : nums) numsSum+=x;//数组和
return totalSum - numsSum;//两数只差就是缺失的数字
}
}
解法三：使用位运算 （使用异或（^）
异或的性质：
- 归零律：任何数和自身进行异或运算，结果为 0，即
a ^ a = 0。例如，5 ^ 5 = 0。 - 恒等律：任何数和 0 进行异或运算，结果是其本身，即
a ^ 0 = a。例如，5 ^ 0 = 5。 - 交换律和结合律：异或运算满足交换律和结合律，也就是
a ^ b ^ c = a ^ c ^ b = b ^ a ^ c等。
规律：
- 对数组中的所有元素进行异或运算，得到ret
- 然后ret遍历[0 ,n],类似消消乐，因为第一次异或后，第二次又去异或会得到0
- 最后0会异或缺失的数字，得到缺失数字本身
class Solution {
public int missingNumber(int[] nums) {
int ret = 0;
for(int num : nums) ret ^= num;
for(int i = 0;i<=nums.length;i++) ret^=i;
return ret;
}
}
3.两整数之和
解法：使用位运算
比如正常使用二进制计算加法
但是，计算机不能直接一步到位计算（它不能进位相加）
- 首先使用(异或)^，进行无进位相加
- 使用&左移1位，找出要进位的1（为什么要左移一位？，因为&后，1是在原位，没有进位）
- 不断重复以上步骤，直到进位数为0
class Solution {
public int getSum(int a, int b) {
while(b != 0){
int x = a ^ b;//算出无进位相加的结果
int y = (a & b) << 1;//计算进位
a = x;
b = y;
}
return a;
}
} 
4.只出现一次的数字 II
解法:使用位图
- 数组中，每一个数的对应的比特位要么为1，要么为0
- 比特位存在上述四种情况
- 把所有数字的对应的比特位相加，模 3 后得到的刚好知道只出现一次数字对应的比特位是多少（因为a是单个）
- 然后如果是比特位是1，那就修改对应的比特位为1（从数字0）
- 修改完之后，得到的二进制位就是只出现一次的数字
不是很难，用脑子回顾一下这个过程
class Solution {
public int singleNumber(int[] nums) {
int ret = 0;
for(int i = 0;i < 32;i++){
int sum = 0;
for(int x : nums){
if(((x>>i) & 1 ) == 1) sum++;//检查是否为1，并累积sum
}
if(sum % 3 == 1){
ret = (1<<i) | ret;//如果为1，就修改当前比特为1
}
}
return ret;
}
} 
5.消失的两个数字
解法：位运算
先认识关于异或^的概念（关于缺失的数字的概念）
解题步骤：
1.先把nums 和 [1 ,length + 2 ]所有的数异或在一起,就会得到两个缺失的数字进行异或。
2.找出a，b两个比特位不同的那一位（一个数字比特位为0，一个数字比特位为1）
3.将所有的数按照diff位不同，分异或两类
代码：
class Solution {
public int[] missingTwo(int[] nums) {
//1.先把所有的数异或在一起
int tmp = 0;
for(int x :nums) tmp^=x;
for(int i = 1;i <= nums.length+2;i++ ){
tmp^=i;
}
//2.找出a，b两个比特位不同的那一位
int diff = 0;
while(true){
if(((tmp>>diff) & 1) == 1) break;
else diff++;
}
//3.将所有的数按照diff位不同，分异或两类
int ret[] = new int[2];
for(int x:nums)
if(((x>>diff) & 1) == 1) ret[1] ^=x;
else ret[0] ^= x;
for(int i = 1;i <= nums.length+2;i++ ){
if(((i>>diff) & 1) == 1) ret[1] ^=i;
else ret[0] ^= i;
}
return ret;
}
} 