【基础算法总结】位运算

算法原理：
根据上面总结的位运算的操作，这道题有两种解法。

代码实现1：

根据上面的第三点，可以判断 n 的二进制里的每一位是否是1，如果是，计数器++。

class Solution
{
public:int hammingWeight(int n){int count = 0;for (int i = 0; i < 32; i++){if ((n >> i) & 1) count++;}return count;}
};

代码实现2：

根据上面的第8点，每次都干掉数 n 的最右侧的1，统计执行的次数即可。

class Solution {
public:int hammingWeight(int n) {int count = 0;while (n){n &= (n - 1);count++;}return count;}
};

算法原理：

这道题就是上一题的进阶题，算法原理同上，加一个循环遍历从0到n的数字，分别计算出每个数字的二进制中1的个数，存入数组中即可。

代码实现：

class Solution 
{
public:vector<int> countBits(int n) {vector<int> ret;for(int i = 0; i <= n; i++){int tmp = i;unsigned int count = 0;while(tmp){tmp &= (tmp-1);count++;}ret.push_back(count);}return ret;}
};

算法原理：

根据上面的操作三，判断这两个数的每一位是否相等，如果不相等，计数器++ 即可。

代码实现：

class Solution 
{
public:int hammingDistance(int x, int y) {int i = 0;int count = 0;for(; i < 32; i++)if(((x >> i) & 1) != ((y >> i) & 1)) count++;return count;}
};

算法原理：
这道题比较简单，有多种解法：一是使用位图思想，二是使用哈希表，三是用数组模拟哈希。

这里介绍位图思想。

用一个 int 变量的32个比特位(实际上只使用26个)来标记这个字符在或不在，0 表示不在，1 表示在。
所以先要判断二进制中的第 n 位是 1 还是 0，如果是 0，就修改成 1，如果已经是 1 了，说明这个字符就已经存在了，返回false。

这里还有一个小的优化点：

由鸽巢原理(抽屉原理)可知，当字符串的长度大于26个时，一定会出现重复字符。

代码实现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'; // 移动的位数// 字符不存在，映射位置的比特位修改成1if (((bitMap >> i) & 1) == 0) bitMap |= (1 << i);else return false;}return true;}
};

代码实现2：使用哈希表
时间复杂度：O(N)
空间复杂度：O(N)

class Solution
{
public:bool isUnique(string astr){if(astr.size() > 26) return false;unordered_map<char, int> hash;for (auto ch : astr){// 判断是否存在if (hash.count(ch) == 0) hash[ch]++;else return false;}return true;}
};

代码实现3：用数组模拟哈希

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

算法原理：
这道题其实和 [二分查找] 系列中的最后一题是一模一样的，题目简单，解法多种。

这里介绍使用位运算。

使用异或运算的规律：
a ^ 0 = a
a ^ a = 0
a ^ b ^ c = a ^ (b ^ c)
可以先把完整的 [0, n] 共 n + 1 个数进行异或，再把这个异或结果异或上题目所给的数据，相同数异或变成0，最后剩下的那个就是缺失的数字。

代码实现：

class Solution 
{
public:int missingNumber(vector<int>& nums) {int ret = 0;for(int i = 0; i <= nums.size(); i++)ret ^= i;for(auto x : nums)ret ^= x;return ret;}
};

如果想要了解其他解法，请点击文章：【二分查找】里的最后一题 [LCR173.点名]。

算法原理：

这道题使用异或运算 – 无进位相加。
先算出无进位相加的结果，再算出进位，再把两者相加，但是不能使用加法，要重复执行上面两个操作，直到进位为 0 为止。

代码实现：

class Solution 
{
public:int getSum(int a, int b) {int tmp = a ^ b; // 无进位相加的结果int res = (a & b) << 1; // 算出进位// 当进位不为0时，重复上面操作while(res){a = tmp;b = res;tmp = a ^ b;res = (a & b) << 1;}return tmp;}
};

算法原理：

这道题很简单，就是对异或运算律(a ^ a = 0)的简单使用。

代码实现：

class Solution 
{
public:int singleNumber(vector<int>& nums) {int ret = 0;for(auto x : nums)ret ^= x;return ret;}
};

算法原理：

把所有数据的第 i 个二进制位相加，和会出现下面4种情况：

用相加的和取模3(%3)，如果是三个相同的数，它们的第 i 个二进制位相加结果模3为 0，如果等于 1，说明这个二进制位是那个只出现一次的数的，就把它映射到另一个 int 变量的对应的二进制位上。

代码实现：

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)sum += ((x >> i) & 1); // 把所有数字的第i个二进制位相加// 如果等于1，说明是出现一次的，把1映射到相应的二进制位if(sum % 3 != 0) ret |= (1 << i);  }return ret;}
};

算法原理：

其实根据 [136.只出现一次的数字] 对这道题是有思路的，就是相同的数异或在一起就变成0了，关键就是如何把相同的数放到一组？

代码实现：

class Solution 
{
public:vector<int> singleNumber(vector<int>& nums) {int tmp = 0;// 把所有数据异或在一起for(auto x : nums)tmp ^= x;// 找出tmp中，比特位上为1的位置int i = 0;for(; i < 32; i++)if((tmp >> i) & 1) break;// 根据i的位置把数据分成两类,分别异或int a = 0, b = 0;for(auto x : nums)if((x >> i) & 1) a ^= x;else b ^= x;return {a, b};}
};

算法原理：
这道题本质上是 [268.消失的数字] 和 [260.只出现一次的数字III] 的结合题。

代码实现：

class Solution 
{
public:vector<int> missingTwo(vector<int>& nums) {int tmp = 0;// 把所属异或在一起for(auto x : nums) tmp ^= x;for(int k = 1; k <= nums.size()+2; k++) tmp ^= k;// 找到tmp中，比特位上为1的那一位int i = 0;for(; i < 32; i++)if((tmp >> i) & 1) break;// 根据第i位的不同，把所有数据分成两类int a = 0, b = 0;for(auto x : nums)if((x >> i) & 1) a ^= x;else b ^= x;for(int j = 1 ; j <= nums.size()+2; j++)if((j >> i) & 1) a ^= j;else b ^= j;return {a, b};}
};