算法 | 位运算（哈希思想）
位运算
| & | 与 | 两个位都为1时，结果才为1（有0为0） |
| | | 或 | 两个位都为0时，结果才为0（有1为1） |
| ^ | 异或 | 两个位相同为0，相异为1 |
| ~ | 取反 | 0变1，1变0 |
| << | 左移 | 各二进位全部左移若干位，高位丢弃，低位补0 |
| >> | 右移 | 各二进位全部右移若干位，高位补0或符号位补齐 |
判定字符是否唯一
面试题 01.01. 判定字符是否唯一 - 力扣（LeetCode）
https://leetcode.cn/problems/is-unique-lcci/description/
题解：
由于题目限制我们不能使用额外的数据结构，我们用位图来解决，位图的原理和哈希表类似。
用 int i=ch-'a' 来记录字母对应的位图的下标，
- 如果该下标在位图中为 1，即 bitmap&(1<<i) == 1，说明该字母在字符串中不唯一；
- 如果该下标在位图中为 0，则该字母在字符串中是唯一的！则把该位置从 0 改为 1.
class Solution {
public:
bool isUnique(string astr) {
if(astr.size()>26) return false;
int bitmap=0;
for(auto ch:astr)
{
int i=ch-'a';
if(bitmap&(1<<i)) return false;
bitmap|=(1<<i);
}
return true;
}
};丢失的数字
268. 丢失的数字 - 力扣（LeetCode）https://leetcode.cn/problems/missing-number/description/
题解：
异或 -- 相同为0，不同为1
即 1 ^ 1 = 0、0 ^ 0 = 0、1 ^ 0 = 1
由运算规则可知，任何二进制数与零异或，都会等于其本身，即 A ^ 0 = A。
异或性质
（1）交换律： A ^ B = B ^ A
（2）结合律： ( A ^ B ) ^ C = A ^ ( B ^ C )
（3）自反性： A ^ B ^ B = A （由结合律可推： A ^ B ^ B = A ^ ( B ^ B ) = A ^ 0 = A）
因为缺失的数字在这两个数组中只出现了1次，而其余数字都出现了2次，出现2次的数字异或后结果为0。
只要把完整的数组和缺失的数组异或在一起，就可以找到缺失的数字！
class Solution {
public:
int missingNumber(vector<int>& nums) {
int n=nums.size();
int ret=0;
for(auto x:nums) ret^=x;
for(int i=0;i<=n;i++) ret^=i;
return ret;
}
};两整数之和
371. 两整数之和 - 力扣（LeetCode）https://leetcode.cn/problems/sum-of-two-integers/description/
题解：
由于不能直接使用加法，只能使用位运算。
把两个数都化为二进制进行相加，二进制相加时，1+1=10，0+0=0，1+0=1，和异或的规则类似，但需要处理进位。
如果两个数都是 1 才需要进位，有一个数不是 1 就不需要进位，这符合 & 的规则。因为进位是向前进 1 位，所以 & 后的结果需要左移 1 位。
把 ^ 和 & 的结果相加起来就可以得到进位后的结果，但是本道题不能使用加法，所以再次 ^ 和 & ，来模拟加法，直到 & 得到的结果为 0，也就是不需要进位时，就可以得到最终结果。
class Solution {
public:
int getSum(int a, int b) {
while(b!=0)
{
int x=(a^b);
int carry =(a&b)<<1;
a=x;
b=carry;
}
return a;
}
};只出现一次的数字 II
137. 只出现一次的数字 II - 力扣（LeetCode）https://leetcode.cn/problems/single-number-ii/description/
题解：
把数组中所有的数相加，对相加得到的和的某一位数字，有如下 4 种情况：3个0 + 0、3个0 + 1、3个1 + 0、3个1 + 1，把这 4 种情况都模3，就可以得到 0、1、0、1，即只出现一次的数字的对应的二进制。
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>>i)&1 == 1) ++sum;
}
sum%=3;
if(sum==1)
ret |=(sum<<i);
}
return ret;
}
};消失的两个数字
面试题 17.19. 消失的两个数字 - 力扣（LeetCode）
题解：
这道题类似丢失的数字，只是丢失的是两个数字。
把缺失数字的数组和完整数字的数组异或在一起，除了 a、b只出现了一次，其余数字出现了两次，所以异或的结果其实就是 a^b，由于 a、b 是不同的数字，即异或的结果中肯定有某一位的数字为1。
我们找出这一位 x（如果有多位的话，找出其中一位即可），就可以把数组的数字分为两类，一类是 x 位上的二进制为 1，一类是 x 位上的二进制为 0，假设 a 的 x 位上的二进制为 0 ，b 的 x 位上的二进制为 1。
对于 x 位上的二进制为 1 的缺失数字的数组和完整数字的数组，a 只出现一次，其余数字都出现 2次，对于 x 位上的二进制为 0 的 b 也是同理，问题就转换为求一个丢失的数字。
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++;
}
//根据 diff位的不同，将所有的数划分为两类来异或
int a=0,b=0;
for(auto x:nums)
{
if(((x>>diff) & 1) ==1) b^=x;
else a^=x;
}
for(int i=1;i<=nums.size()+2;i++)
{
if(((i>>diff) & 1) ==1) b^=i;
else a^=i;
}
return {a,b};
}
};
原文地址：https://blog.csdn.net/2301_76973016/article/details/142712629
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！