判断字符是否唯一
面试题 01.01. 判定字符是否唯一 - 力扣（LeetCode）
思路
此题可以用位运算解决，我们这里使用位图。位图：即定义一个数字将其转换为32个二进制位，将其初始化为0，每个字母代表一位，判断每个位置是否为1，如果为0，则将其加一（相当于记录此位置存在一种字母）；如果为1，则之前这种字母已存在，返回false即可。
代码
bool isUnique(string astr)
{
if (astr.size() > 26) return false;
int bitMap = 0;
for (auto ch : astr)
{
int i = ch - 'a';
if (((bitMap >> i) & 1) == 1) return false;
bitMap |= 1 << i;
}
return true;
}丢失的数字
思路
我们知道，异或运算的性质是相同返回0， 相异返回1，所以我们先创造一个未丢失数字的数组，将其与丢失数字的数组按位异或，相同的值都变成了0，剩余的没有变成0的值即为丢失的数字。
代码
int missingNumber(vector<int>& nums)
{
int ret = 0;
for (auto x : nums) ret ^= x;
for (int i = 0; i <= nums.size(); i++) ret ^= i;
return ret;
}两数之和
思路
按位异或的本质是无进位相加，所以这题我们需要将两数异或并找到进位次数即可。
而按位与的性质是有0则0，所以对于进位，以a,b两数为例，我们选择将两数按位异或的值复制给a，而将两数按位与并向左移1位的值赋值给b（按位与表示两数必须全为1才为1，将得到的值向左移就相当于进位了，而其他的一定至少有一个不为1，因为都为1才进位，所以其他的都变成了0）。
继续循环即可直到没有两位数都为1的情况，即无需进位，最后按位与就会将b变成0，同时，这也是我们循环结束的条件。
代码
int getSum(int a, int b)
{
while (b != 0)//算到进位为0为止
{
int x = a ^ b;
unsigned int carry = (unsigned int)(a & b) << 1;
a = x;
b = carry;
}
return a;
}只出现一次的数字II
137. 只出现一次的数字 II - 力扣（LeetCode）
思路
这题我们将所有数的某一位加起来，因为其他n个数都是相同的，所以有四种情况
3*n + 1 == 3n + 1
3*n == 3n
0 + 1 == 1
0 + 0 == 0
此时我们将得到的值模3，得到的值即为那个只出现一次的数的那一位
代码
int singleNumber(vector<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++;
sum %= 3;
if (sum == 1) ret |= (1 << i);
}
return ret;
}拓展
我们可以总结规律，出现多少次的数我们就将值模多少，这种类型的题目无论元素出现4次还是10次，我们就都可以用这种解法了
消失的两个数字
面试题 17.19. 消失的两个数字 - 力扣（LeetCode）
思路
我们分步骤解决问题
第一步：与丢失的数字那题类似，我们将缺失数字的数组与原数组按位异或，以a,b为例就可以得到a ^ b的值了。
第二步：找出a和b比特位不同的一位diff，从下标为0开始，相异为1，所以需要找到值为1的那一位
第三步：根据diff将数组划分为两类来异或
代码
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 (int 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 };
}位运算解题技巧
按位与 & :有0则0
按位或 | :有1则1
按位异或 ^: 相同为0， 相异为1/不进位相加
1.给一个数n， 确定它的二进制表示中的第x位是0还是1
(n >> x) & 1 == 0 -> 0 / 1 -> 1
2.将一个数n的二进制表示的第x位修改成1
n |= (1 << x)
3.将一个数n的二进制表示的第x位修改成0
n &= ~(1 << x)
4.提取一个数(n)二进制表示中最右侧的1
n & (-n)
5.去除一个数(n)二进制表示中最右侧的1
n & (n - 1)
6.异或运算律
a ^ 0 = a
a ^ a = 0
a ^ b ^ c = a ^ (b ^ c)(不考虑顺序)