【leetcode】位运算专题_位运算的题目

文章目录

• 1. 位1的个数
• 2. 汉明距离
• 3. 判定字符是否唯一
• 4. 丢失的数字
• 5. 两整数之和
• 6. 只出现一次的数字Ⅱ
• 7. 只出现一次的数字Ⅲ
• 8. 消失的两个数字

首先我们先来复习一下几种位运算

1. & 与：都为1，才为1
2. | 或： 有1则1
3. ^ 异或：相同为0，相异为1（无进位相加） n ^ 0 = n、n ^ n = 0 、a ^ b ^ C == a ^ （b ^ c）
4. ! 取反：按位取反，0变1，1变0

涉及到位运算，我们也要考虑位图的思想。

在这里我们也要给出两个位运算经常用的操作

1. 提取一个数n二进制表示中最右侧的1
   n & - n
   
   2. 删除一个数n二进制表示中最右侧的1
   n & (n-1)
   

根据上面位运算的相关内容，我们就可以做下面的题目了

1. 位1的个数

题目链接

根据上面的描述，就是求一个数对应二进制位中1的个数。所以，我们可以使用 n & (n-1)来去除最右侧的1，直到该数变成0，就没有1了。去除了几次，就有几个1

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

2. 汉明距离

题目链接

题目要求求两个数二进制位不同的个数，此时就可以使用 异或操作 得到不同的位，即可将题目转化为求一个数二进制位中1的个数。

 int hammingDistance(int x, int y) { int tmp = x ^ y; int count = 0; while(tmp) { tmp &= tmp - 1; count++; } return count; }

3. 判定字符是否唯一

• 解法一：暴力遍历，“双指针”思想遍历，重复字符直接返回false。
• 解法二：使用哈希表建立映射关系，遍历哈希表，有大于1的就返回false；否则返回true。
• 解法三：采用位图的思想，使用26个比特位标记字符，如果当前遍历的字符其对应比特位为1了，说明有重复的字符，返回false；当前字符对应比特位为0，则之前没有出现过，当前出现了，比特位设置为1。
  (优化：字符串长度大于26，则一定有重复的，即“鸽巢原理”)

 bool isUnique(string astr) { if(astr.size() > 26)//优化 return false; int bitset = 0; for(int i=0; i< astr.size(); i++) { //如果当前遍历字符出现过 int t = astr[i] - \'a\'; if(((bitset >> t) & 1) == 1) return false; //当前遍历字符没有出现过,将该位设置为1，使其出现 else  bitset |= 1 << t; } return true; }

4. 丢失的数字

题目链接

根据题目可知，数组中原本应该是[0,n] n+1个数，此时少了一个，要找到少的那一个。

• 解法一：0-n求和，使用和再减去数组中的元素，和中最后剩余的数就是丢失的数字。
• 解法二：根据异或运算的“交换律”，直接先将0-n异或起来，再异或数组中的元素，最后异或的结果就是丢失的数字。
  

 int missingNumber(vector<int>& nums) { int num = 0; //先异或[0,n] for(int i=0; i <= nums.size(); i++) num ^= i; //再异或数组元素 for(auto& e : nums) num ^= e; return num; }

5. 两整数之和

题目链接

题目要求不得使用+、-运算符，那我们只能从二进制位下手了。

两数的二进制位相加，每一位相加的结果无非就是1和0。是1时不存在进位；是0时可能存在进位。

那我们先将不进位的结果记录下来，也就是异或操作。然后再获得进位，两个数对应位都为1才会产生进位，所以让两数相与，即可获得要进位的位置。

 int getSum(int a, int b) { while(b) { int x = (a ^ b);// 无进位相加 int y = (a & b) << 1;//记录进位 a = x; b = y; } return a; }

6. 只出现一次的数字Ⅱ

题目链接

该题目类似于文章第三题

• 解法一：暴力枚举
• 解法二：使用哈希表，遍历完成后，哈希表中为1的就是目标元素
• 解法三：使用位图的思想，由于每个数字都可用32个比特位来表示，我们可以通过遍历所有元素的第i个比特位，如果该比特位是1的元素的个数 count % 3 = = 1，则表明目标数和其余3*n个数该位置都为1，或者只有目标数该位置为1，那么就可以将该位置设置为1，当遍历完32位后，重新被设置的数就是目标数。

 int singleNumber(vector<int>& nums) { int num = 0; for(int i=0; i < 32; i++) { int count = 0;//记录当前比特位为1的个数 for(auto& e : nums) { //当前元素的第i个比特位为1，记录个数 if((e >> i) & 1 == 1)  count++; } if(count % 3 == 1) //要么 3*n+目标数 的该位为1，要么目标数该位为1 num |= 1 << i; } return num; }

7. 只出现一次的数字Ⅲ

题目链接

• 由于仅有两个数字出现了一次，那么所有数字相异或的结果就是两个仅出现一次数字异或的结果。
• 异或的结果中为1的位就是二者不同的位，因此我们可以利用一个不同位将两者分开。
• 其余出现两次的数该位一定相同，因此会被分到一边，对两边的数字各自异或，结果就是那两个仅出现一次的数。
  

vector<int> singleNumber(vector<int>& nums) { int sum = 0; //先将所有数异或再一起 for(auto& e : nums) sum ^= e; //此时sum中就是两个仅出现一次的数异或的结果 int t = 0; for(int i=0; i < 32; i++) { //寻找二者不同的一个二进制位 if((sum >> i) & 1 == 1) { t = i; break; } } int x = 0, y = 0; //根据不同的二进制位将二者分开 for(auto& e : nums) { if((e>>t) & 1 == 1)//第t位为1的分到一边 x ^= e; else y ^= e; //不为1的分到另外一边 } return {x,y}; }

8. 消失的两个数字

题目链接

该题目就是 (3.丢失的数字 + 7.只出现一次的数字Ⅲ) 的整合。

• 首先，我们可以使用 [1,N] 与数组元素异或，异或的结果就是丢失那两个数据异或的结果。
• 然后根据异或结果，找出两数字不同的一个二进制位
• 通过和那一个不同的二进制位相&，将 [1,N] 与数组元素进行分类。分类后的结果就是每一边数字都出现了两次，仅两个丢失的数字出现了一次。

 vector<int> missingTwo(vector<int>& nums) { int sum = 0; int n = nums.size() + 2; //先异或[1,n] for(int i=1; i<= n; i++) sum ^= i; //再异或数组元素 for(auto& e : nums) sum ^= e; //此时sum中就是两丢失数字异或的结果 //找出两丢失数字一个不同的二进制位 int t = 0; for(int i=0; i < 32; i++) { if(((sum >> i) & 1) == 1) { t = i; break; } } //根据这一个位，将[1,n]与数组元素进行分类 int x = 0, y = 0; for(int i=1; i <= n; i++) { if(((i>>t) & 1) == 1) x ^= i; else y ^= i; } for(auto& e : nums) { if(((e>>t) & 1) == 1) x ^= e; else y ^= e; } return {x,y}; }