【刷题】位运算

消失的两个数字 

消失的两个数字

“单身狗”进阶版思路

class Solution {
public:vector<int> missingTwo(vector<int>& nums) {int ret = 0;int n = nums.size();for(int i = 0; i < n; i++){ret ^= (nums[i] ^ i);}ret ^= (n ^ (n + 1) ^ (n + 2));// 按位异或的规则是相异为1// 找出从最低位开始第一次出现 1 的位置，这个位置一定对应两个数字的二进制位是一个为0 ，一个为1int flag = 0;while(!((ret >> flag) & 1)) flag++;vector<int> v1;vector<int> v2;for(int i = 0; i < n; i++){if(((nums[i] >> flag) & 1) == 1) v1.push_back(nums[i]);else v2.push_back(nums[i]);}for(int i = 1; i < n + 3; i++){if(((i >> flag) & 1) == 1) v1.push_back(i);else v2.push_back(i);}// 对 v1 和 v2 分别操作vector<int> v3;int tar = 0;for(int i = 0; i < v1.size(); i++){tar ^= v1[i];}v3.push_back(tar);tar = 0;for(int i = 0; i < v2.size(); i++){tar ^= v2[i];}v3.push_back(tar);return v3;}
};

只出现一次的数字 II

只出现一次的数字 II

思路：将所有数字的每一位比特位相加，这些比特位的和有如下规律：

只需要定义一个整形变量，通过上述方法计算出它的每一个比特位即可！ 

class Solution {
public:int singleNumber(vector<int>& nums) {int ret = 0; // 只出现一次的数字for(int i = 0; i < 32; i++){// 修改第 i 位的值// 将每个数的第 i 个比特位加起来int sum = 0;for(int j = 0; j < nums.size(); j++){sum += ((nums[j] >> i) & 1);}sum %= 3;ret |= (sum << i);} return ret;}
};

两整数之和 

两整数之和

class Solution {
public:int getSum(int a, int b) {// ^ 是无进位相加，只需要每次找到进的位，再相加，等到进位为 0 的时候，就结束了int sum = a ^ b;size_t carry = (size_t)((a & b) << 1); // carry 是进的位while(carry){a = sum, b = carry;sum = a ^ b;carry = size_t((a & b) << 1);}return sum;}
};

^ 异或运算是：两个数对应比特位相同为0，相异为1，也叫 不进位相加

只需要利用按位异或运算符进行不进位相加运算，然后每次加上它的进位即可！直到进位为0！

判断字符是否唯一

判定字符是否唯一

两种方法：哈希表和位图（位图是进阶方法）

哈希表

class Solution {
public:bool isUnique(string astr) {int a[26] = { 0 };for(int i = 0; i < astr.size(); i++){a[astr[i] - 'a'] ++ ;}for(int i = 0; i < 26; i++){if(a[i] > 1) return false;}return true;}
};

位图

和哈希表思路一样，但是将标记存在32个比特位中，利用位运算来控制比特位的值！

class Solution {
public:bool isUnique(string astr) {int n = astr.size();if(n > 26) return false;int bit_set = 0; // 一个位图整形for(int i = 0; i < n; i++){int a = bit_set >> (astr[i] - 'a'); // bit_set 移位后的数if((a & 1) == 0) {bit_set |= (1 << (astr[i] - 'a'));}else if((a & 1) == 1) return false;}return true;}
};