一、常见位运算总结
1. 给一个数n ，判断他的第x位是0还是1
答案： (n >>x) & 1
2. 给一个数n，将他的第x位置为1
答案：n |= (1<<x)
3. 给一个数n，将他的第x位置为0
答案：n &= (1<<x)
4. 提取一个数n二进制最右侧的1
答案：n & -n
解析：这个步骤的本质就是将最后面那个1前面的位全部取反
5.将一个数n的二进制最右侧的1置为0
答案：n &（n-1）
解析：这个很容易理解，n-1 会将n最右边的1给借位掉用于-1，而最右边1之前的位都不会改变
二、（面试题）判定字符是否唯一
题目链接：
面试题 01.01. 判定字符是否唯一 - 力扣（LeetCode）
题目介绍：
实现一个算法，确定一个字符串 s 的所有字符是否全都不同。
0 <= len(s) <= 100s[i]仅包含小写字母- 如果你不使用额外的数据结构，会很加分。
思路1：
利用哈希表，在遍历字符时，先判断它是否在哈希表中，如果在就返回false，否则就把他加入到哈希表中
class Solution {
public:
bool isUnique(string astr) {
unordered_map<char,int> hash;
for(auto e:astr)
{
if(hash.count(e))
return false;
else
hash[e]++;
}
return true;
}
};思路2：
对上面的思路进行优化，利用一个整形数字的每一个比特位作为哈希表，另外我们还可以利用'鸽巢原理'进行优化，因为字母只有26个，如果字符串的长度大于26，那一定存在重复，直接返回false
class Solution {
public:
bool isUnique(string astr) {
if(astr.size() > 26) return false;
int ret=0; //位图
for(auto e:astr)
{
int n=e-'a';
if(((ret>>n)&1)==1)
{
return false;
}
ret|=(1<<n);
}
return true;
}
};三、两整数之和
题目链接：
题目介绍：
给你两个整数 a 和 b ，不使用 运算符 + 和 - ，计算并返回两整数之和。
-1000 <= a, b <= 1000
思路：
利用异或和按位与操作实现：
异或的本质就是无进位相加
而按位与的操作本质就是可以得到进位
然后结果就是他们两个相加，不过在相加之前，还需要将按位与后的结果向左移动1位，因为我们要得到的是进位后的结果。但是题目中不让用+ -，所以我们就重复上述操作，直到进位全为0，就得到结果了。
将 carry定义为 unsigned int 类型是为了避免符号扩展的问题，并确保在计算过程中可以处理可能的大数值进位，而不会因溢出而丢失信息。
class Solution {
public:
int getSum(int a, int b) {
//10101011
//11001010
int ret=0;
while(b!=0)
{
ret=a^b;
unsigned int carry=(unsigned int)(a&b)<<1;
a=ret;
b=carry;
}
return a;
}
};
四、只出现一次的数字II
题目链接:
137. 只出现一次的数字 II - 力扣（LeetCode）
题目介绍：
给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。
1 <= nums.length <= 3 * 104-231 <= nums[i] <= 231 - 1nums中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次
思路：
对于结果的每一个比特位来讲，它要么是它要么是3n+0或者3n+1，0和1表示出现一次那个那个比特位的大小，如果我们%3的话，可以发现结果是与出现一次的那个比特位大小是一样的。
按照上面的思路，我们就可以快速定位到 ret 的「⼀个比特位上」的值是 0 还是 1 。这样，我们通过 ret 的每⼀个比特位上的值，就可以将 ret 给还原出来。
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ret=0;
//初始化ret的每一个比特位
for(int i=0;i<32;i++)
{
int sum=0;
for(auto e:nums)
if(e>>i&1==1)
sum++;
ret|= ((sum%3)<<i);
}
return ret;
}
};五、消失的两个数字
题目链接：
面试题 17.19. 消失的两个数字 - 力扣（LeetCode）
题目介绍：
给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？
以任意顺序返回这两个数字均可。
nums.length <= 30000
思路：
按照 消失的一个数字 这个题的思路，首先，如果我们将数组的所有结果和1~n的全部数字异或一边的话， 这个结果其实就是消失的那两个数字异或的结果。现在我们就要想一个方法区分出这两个数，由于异或是相同为0，相异为1，对于这两个消失的数字来说，这个结果比特位为1的那个位他们俩肯定一个是1一个是0。
所以我们就可以按照这个区别，将数组分为两个部分，一部分是该位为1的，另一部分是该位为0的，这样这个题就转变为了找消失的一个数字的那个题，我们就按照这个题的思路，定义a和b，让整个数组和1~n的数，那个位为1的数与a异或，位0的数与b异或。
就算我们将数组分成两部分也不影响，因为对于没有消失的数字我们他们都在一个部分内被异或了两次。
class Solution {
public:
vector<int> missingTwo(vector<int>& nums)
{
int ret = 0;
for(auto& num : nums) ret ^= num;
for(int i = 1; i <= nums.size()+2; i++) ret ^= i;
//ret = a ^ b
int count = 0;
while(1)
{
if(((ret >> count) & 1) == 1) break;
else count++;
}
int a = 0;
int b = 0;
for(auto& num: nums)
{
if(((num >> count) & 1) == 1) a ^= num;
else b^=num;
}
for(int i = 0; i <= nums.size()+2; i++)
{
if(((i >> count) & 1) == 1) a ^= i;
else b^=i;
}
return {a,b};
}
};