1. 判定字符是否唯一
题目链接：判定字符是否唯一
题目描述：
算法思路：位运算，位图
当字符串长度大于 26 时，那么一定存在重复字符，直接返回即可。
利用位图，每一个比特位代表一个字符，一个 int 类型的变量足够表示所有的小写字母，比特位是 0 表示这个字符没有出现过，比特位里面的值是 1 表示该字符出现过。
算法代码：
public boolean isUnique(String astr) {
if (astr.length() > 26) return false;
// 位图
int bitMap = 0;
for (int i = 0; i < astr.length(); i++) {
int x = astr.charAt(i) - 'a';
if (((bitMap >> x) & 1) == 1) return false;
bitMap |= (1 << x);
}
return true;
}
2. 丢失的数字
题目链接：268. 丢失的数字
题目描述：
算法思路：位运算
异或的运算律，a ^ a = 0，因此可以使用异或 ^ 消消乐，先将 nums 数组里的数全部异或在一起，然后将 [0, n] 区间内的数也异或在一起，那么得到的就是只出现一次的数。
算法代码：
public int missingNumber(int[] nums) {
int ret = 0;
for (int i = 0; i < nums.length; i++) {
ret ^= nums[i];
}
for (int i = 0; i <= nums.length; i++) {
ret ^= i;
}
return ret;
}
3. 两整数之和
题目链接：371. 两整数之和
题目描述：
算法思路：位运算
异或操作是无进位相加，那么 a & b 找到进位，并且左移 1 位，当进位为 0 时，异或的结果就是两数之和。
算法代码：
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;
}
4. 只出现一次的数字 ||
题目链接：137. 只出现一次的数字 ||
题目描述：
算法思路：位运算
在整个数组中，有一个数出现一次，其余都出现三次，那么将每一个比特位相加并 % 3，那么得出的就是单次出现元素对应的比特位，将 32 位都这样求出来就可以还原这个数。
算法代码：
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++;
}
sum %= 3;
if (sum == 1) ret |= (1 << i);
}
return ret;
}
5. 消失的两个数
题目链接：消失的两个数
题目描述：
算法思路：
将数组和 1 到 n 的数全部异或在一起，可以得到缺失两个数的异或。可以根据异或比特位为 1 的位置将数组分成两部分，一部分为该比特位为 0，一部分该比特位为 1。然后分别将两个数组的两部分异或在一起，就分别得到了缺失的数。
算法代码：
public int[] missingTwo(int[] nums) {
int tmp = 0;
for (int i = 0; i < nums.length; i++) {
tmp ^= nums[i];
}
for (int i = 0; i <= nums.length + 2; i++) {
tmp ^= i;
}
int diff = 0;
while (true) {
if (((tmp >> diff) & 1) == 1) break;
else diff++;
}
int ret[] = new int[2];
for (int x : nums) {
if (((x >> diff) & 1) == 1) ret[0] ^= x;
else ret[1] ^= x;
}
for (int i = 0; i <= nums.length + 2; i++) {
if (((i >> diff) & 1) == 1) ret[0] ^= i;
else ret[1] ^= i;
}
return ret;
}
