常见位运算总结

重点 :

---

1. 位1的个数

算法思路:

这道题就用到了我们总结的那个第七个方法, 干掉最右侧的1, 知道全部为0位置, 记录并返回干掉次数即可.

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

法二: 遍历每一位进行按位与操作, 并没有方法一效率高

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

2. 比特位计数

算法思路: 本题也就是求出0到n中每一个数的比特位中1的个数, 很容易想到的方法就是,遍历数组, 按照上一题的思路求出i的1比特位即可.

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

---

3. 汉明距离

算法思路:

也就是求出两个数的比特位不同的个数, 首先对两正数进行异或运算, 不同为1, 然后求出tmp中1的个数, 沿用之前的方法, 先找出最右侧的1, 然后干掉最右侧的1, 记录次数即可.

class Solution {
public:int hammingDistance(int x, int y) {int ret = 0;int tmp = x ^ y;while(tmp){tmp &= (tmp-1);ret++;}return ret;}
};

4. 只出现一次的数字

算法思路: 仅需将所有数字进行异或, 相同的就被消去了, 最后的数字即为结果.

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

---

5. 只出现一次的数字Ⅲ

算法思路: 首先将数组进行异或处理, 结果就是最后两个不同的数字异或的结果, 因为这两个数字不相同, 所以一定有比特位异或的结果为1, 我们仅需据此进行划分为两组即可, 这里我们默认查找最右侧的1, 然后据此进行划分, 分别进行异或, 最后返回分别异或的结果.

class Solution {
public:vector<int> singleNumber(vector<int>& nums) {int ret = 0, tmp = 0;for(auto& e : nums)tmp ^= e;int pos = -1;for(int i = 0; i < 32; i++){if((tmp & 1) == 1){pos = i;break;}tmp = tmp >> 1;}int x1 = 0,x2 = 0;for(auto& e : nums){if(((e >> pos) & 1) == 1)x1 ^= e;else x2 ^e;}return {x1,x2};}
};

---

6. 判定字符是否唯一

本道题可以采用位图的方法进行优化, 因为数据范围只有小写字母, 我们进行一个int的比特位当成哈希表来用即可, 1和0进行两种状态的标记, 处理之前还可以使用鸽巢原理进行一下优化, 也就是26个字母如果字符串长度超过26那么一定有相同的字符串, 这时候直接返回false即可

class Solution {
public:bool isUnique(string astr) {int n = astr.size();if(n > 26)  return false;int bitmap = 0;for(auto& x : astr){int l = x - 'a';if(((bitmap >> l) & 1) == 1)return false;bitmap |= 1 << l;}return true;}
};

7. 丢失的数字

算法思路: 仅需进行异或操作, 将ret和数组进行异或并且和0到size之间的所有i进行异或即可.

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;}
};

8. 两正数之和

算法思路: 本题要求不能使用+ 和 - 运算符将两个数进行相加, 开始总结位运算的时候, 我们也说过^表示的就是我进位相加, 但是进位怎么办, 两数&的结果即为进位, 但是进位并不是加到本位上的, 应该加到前一位, 所以结果我们要进行左移然后相加, 那么问题又来了, 不让使用+怎么进行相加呢, 其实我们在重复上面的操作, 循环即可, 直到进位为0.

class Solution {
public:int getSum(int a, int b) {while(b != 0){int add = a ^ b;int carry = (a & b) << 1;a = add;b = carry;}return a;}
};

---

9. 只出现一次的数字Ⅲ

算法思路: 理解题意即可知, 这些数字的每一个bit为相加的结果要么是三的倍数,也就是ret的这一位是0, 要么被三整除余数为1, 也就是ret的这一位是1

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);if(sum % 3 == 1)ret |= (1 << i);}return ret;}
};

10. 消失的两个数字

算法思路: 首先先将nums中的每一个数和0到N之间每一个数进行异或, 结果为两个数异或的结果, 然后找出1那个位置, 进行划分即可, 分成两组, 再次进行分别异或, 即可得出结果.

class Solution {
public:vector<int> missingTwo(vector<int>& nums) {int tmp = 0;for(int i = 1; i <= nums.size() + 2; i++)tmp ^= i;for(auto x : nums)tmp ^= x;int dif = 0;while(1){if(((tmp >> dif) & 1) == 1) break;dif++;}int a = 0, b = 0;for(int i = 0; i <= nums.size()+2; i++){if(((i >> dif) & 1) == 1)a ^= i;else b ^= i;}for(auto x : nums){if(((x >> dif) & 1)== 1)a ^= x;else b ^= x;}return {a,b};}
};

---

完