目录
常见位运算总结
leetcode%E9%A2%98%E7%9B%AE-toc" style="margin-left:40px;">leetcode题目
一、位1的个数
二、比特位计数
三、 汉明距离
四、只出现一次的数字
五、只出现一次的数字 III
六、判断字符是否唯一
七、丢失的数字
八、两整数之和
九、只出现一次的数字 II
十、消失的两个数字
常见位运算总结
1.基础位运算
位运算有很多，此处重点强调三个:
&: 有0就是0
|: 有1就是1
^: 相同为0,相异为1/无进位相加
2.给一个数，确定它的二进制位中的第x位是0还是1 ---> (n >> x) & 1
(n >> x) & 1, 结果为0，则第x位是0；结果为1，则第x位是1
注意:我们默认第x位是从低位到高位的，也就是从右到左数的，并且最低位默认是第0位，这样就可以和右移操作符对应了！如下所示，如果想让第3位的1来到最低位，只需要 n >> 3即可
3.将一个数n的二进制表示的第x位修改成1 ---> n |= (1 << x)
只想把如下图所示的0修改成1，只需要给这一位按位或1，其他位按位或0即可！
4.将一个数n的二进制表示的第x位修改成0 ---> n &= (~(1<<x))
只想把如下图所示的1修改成0，只需要给这一位按位与0，其他位按位与1即可！ 而按位的这个数字可以这样得到: ~(1<<x)
5.位图的思想
本质是个哈希表，不过采用的是一个整形变量的32的比特位来记录信息，所以上面的2，3, 4本质都是在为位图做铺垫，比如想判断位图的某一位是0还是1, 0改1/1改0呀 等等操作
6.提取一个数 n 二进制表示中最右侧的1 (lowbit) ---> n&(-n)
提取一个数 n 二进制表示中最右侧的1 意思 是将最右侧的1保留，其他位都变成0
7.干掉一个数n二进制表示中最右侧的1 ---> n&(n-1)
8.位运算的优先级 --- 能加括号就加括号
9.异或运算的运算律
a^0 = a
a^a = 0
(a^b)^c = a^(b^c) ---> ^的无进位相加可以证明(只要出现两个1，加完就是0，和1的顺序无关)
leetcode%E9%A2%98%E7%9B%AE">leetcode题目
一、位1的个数
191. 位1的个数 - 力扣（LeetCode）
https://leetcode.cn/problems/number-of-1-bits/description/
class Solution {
public:int hammingWeight(int n) {int count = 0;for(int i = 0 ; i < 32; i++){if(((n >> i) & 1) == 1)count++;} return count;}
};二、比特位计数
338. 比特位计数 - 力扣（LeetCode）https://leetcode.cn/problems/counting-bits/description/
class Solution {
public:vector<int> countBits(int n) {vector<int> ret;for(int i = 0; i <= n; i++){int count = 0;for(int j = 0; j < 32; j++){if((i >> j) & 1 == 1)count++;}ret.push_back(count);}return ret;}
};三、 汉明距离
461. 汉明距离 - 力扣（LeetCode）https://leetcode.cn/problems/hamming-distance/description/
class Solution {
public:int hammingDistance(int x, int y) {int count = 0;for(int i = 0; i < 32; i++){if( ((x >> i) & 1) ^ ((y >> i) & 1) == 1)count++;}return count;}
};四、只出现一次的数字
136. 只出现一次的数字 - 力扣（LeetCode）https://leetcode.cn/problems/single-number/1.题目解析
给一个数组，其中有1个数只出现了一次，其余数都出现了两次
2.算法分析
此类题目很典型，题目本质就是有一堆数出现了偶数次，只有一个数出现了奇数次，要找到这个数，显然可以用异或操作来解决，由异或的运算律知，a^a=0, a^0=a, 因此我们可以把所有数异或在一起，最终的结果就是只出现一次的数字
3.算法代码
class Solution {
public:int singleNumber(vector<int>& nums) {int x = 0;for(auto& e : nums)x ^= e;return x;}
};五、只出现一次的数字 III
260. 只出现一次的数字 III - 力扣（LeetCode）https://leetcode.cn/problems/single-number-iii/1.题目解析
本题目是有两个数字出现了一次，其余数字都出现了两次，求只出现一次的两个数字
2.算法分析
1.将所有的数异或在一起
因为其余数都出现了两次，所以异或的最终结果就是只出现一次的两个数字异或的结果x
2.找到x最右侧的1是哪一位
因为只出现一次的两个数字不同，所以x结果不为0， 那么x中一定有某一位是1，找到最右侧的1是哪一位(pos)， 而只出现1次的两个数字在第pos位上一定不同，因为异或结果是1
3. 根据最右侧1的那一位，可以将数组元素划分位两组，一组的元素pos位是1，一组的元素pos位是0，而同一个出现两次的数字必然被划分到同一组，两个只出现1次的数字被划分到了不同的组，于是问题就转化成了分别求两组中"只出现一次的数字", 也就是题目四
3.算法代码
class Solution {
public:vector<int> singleNumber(vector<int>& nums){//1.将所有的数字异或在一起int x = 0;for(auto& e : nums)x ^= e;//2.找到x最右侧的1是哪一位int pos = 0;for(int i = 0; i < 32; i++){if(((x >> i) & 1) == 1){pos = i;break;}}//3.分类按位异或int ret1 = 0, ret2 = 0;for(auto& e :nums){if(((e >> pos) & 1) == 1) ret1 ^= e;elseret2 ^= e;}return {ret1, ret2};}
};六、判断字符是否唯一
面试题 01.01. 判定字符是否唯一 - 力扣（LeetCode）https://leetcode.cn/problems/is-unique-lcci/1.题目解析
判断字符串中的字符是否唯一
2.算法分析
解法一:哈希表
1.遍历数组，如果字符不存在，则加入哈希表，存在则返回false, 遍历完之后返回true
2.题目说数组只包含小写字母，因此我们不用创建真的哈希表，只需要创建一个大小为26个int的数组即可~
解法二:位图思想
由解法一第2点知，我们只需要创建一个大小为26个int的数组，可以进一步优化，哈希表的目的就是为了判断字符是否已经出现，因此我们只需要一个int变量，int变量有32位，我们只需要用到较低的26位即可，比特位为1，表示字符已经存在，比特位为0，表示字符不存在;
小优化:
一共有26个字符，如果字符串的长度超过26了，根据鸽巢原理，字符串中一定有重复字符
3.算法代码
class Solution {
public:bool isUnique(string astr) {if(astr.size() > 26) //利用鸽巢原理优化return false;int bitmap = 0;for(auto& e : astr){int x = e - 'a'; //第x位if(((bitmap >> x) & 1) == 0) //判断第x位是否是0bitmap |= (1 << x); //将第x位修改成1elsereturn false;}return true;}
};
七、丢失的数字
268. 丢失的数字 - 力扣（LeetCode）https://leetcode.cn/problems/missing-number/1.题目解析
给定一个包含区间[0, n]中的n个数的数组，求缺失的数字
2.算法分析
解法一:哈希表
创建一个大小为n的哈希表，遍历原数组，建立映射关系；遍历哈希表，找出值为0的位置返回
解法二:高斯求和
(首项+尾项)*项数/2 - 数组所有元素之和
解法三:位运算
将原始数组所有元素 与 [0, n] 所有的数字都异或在一起，最终结果就是缺失的数字
3.算法代码
解法一:哈希表
class Solution {
public:int missingNumber(vector<int>& nums) {int n = nums.size();int hash[10000] = {0};for(auto& e : nums)hash[e]++;for(int i = 0; i <= n; i++)if(hash[i] == 0)return i;return -1;}
};解法二:高斯求和
class Solution {
public:int missingNumber(vector<int>& nums) {int n = nums.size();int sum = (0 + n) * (n+1) / 2;for(auto& e : nums)sum -= e;return sum; }
};解法三:位运算
class Solution {
public:int missingNumber(vector<int>& nums) {int ret = 0, n = nums.size();for(auto& e : nums)ret ^= e;for(int i = 0; i <= n; i++)ret ^= i;return ret;}
};八、两整数之和
371. 两整数之和 - 力扣（LeetCode）https://leetcode.cn/problems/sum-of-two-integers/1.题目解析
求两数之和，但是不能使用 '+' '-'
2.算法分析
不能使用加减法所以大概率是用位运算，使用的就是异或运算，因为异或运算可以用"无进位相加"来解释，所以我们还要求出进位！只有1和1无进位相加会产生进位1， 0和1 或者 1和0 无进位相加后进位都是0，因此可以采用按位与记录进位情况, 但是要注意进位是加到了前一位上面，因此还要 << 1
例如下面求 a(13) + b(28)
3.算法代码
class Solution {
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;}
};九、只出现一次的数字 II
137. 只出现一次的数字 II - 力扣（LeetCode）https://leetcode.cn/problems/single-number-ii/1.题目解析
给定一个数组，有1个数只出现了1次，其余数都出现了3次，找到只出现了1次的数字
2.算法分析
数组中所有数字某一个比特位之和无非四种情况:
3n个0 + 0 = 0
3n个0 + 1 = 1
3n个1 + 0 = 3n
3n个1 + 1 = 3n + 1
规律: 所有数字某个比特位加完之后 对 3取模的结果分别是: 0, 1, 0, 1, 刚好对应只出现1次的数字的那个比特位，因此我们只需要定义一个最终结果变量ret, 循环32次，依次算出数组所有数字的每一个比特位之和，然后 % 3， 结果是1，就将ret的这一位修改成1，否则就修改成0!
3.算法代码
class Solution {
public:int singleNumber(vector<int>& nums) {int ret = 0;for(int i = 0; i < 32; i++){int sum = 0;for(int x : nums) //计算nums中所有的数的第i位的和if(((x >> i) & 1) == 1)sum++;sum %= 3;if(sum == 1) ret |= 1 << i; //将最终结果的第i位修改成1}return ret;}
};十、消失的两个数字
面试题 17.19. 消失的两个数字 - 力扣（LeetCode）https://leetcode.cn/problems/missing-two-lcci/description/1.题目解析
数组大小为n, 则数组中元素应该是1~n+2, 但是缺了两个数字，请找到缺失的两个数字
2.算法分析
转化成题目七+题目五
3.算法代码
class Solution {
public:vector<int> missingTwo(vector<int>& nums) {//1.将所有的数异或在一起int x = 0;for(auto e : nums)x ^= e;for(int i = 1; i <= nums.size()+2; i++)x ^= i;//2.找到x中比特位为1的位置int pos = 0;for(int i = 0 ; i < 32; i++){if(((x >> i) & 1) == 1){pos = i;break;}}//3.划分位两类来进行异或int ret1 = 0, ret2 = 0;for(auto& e : nums){if( ((e >> pos) & 1) == 1)ret1 ^= e;else ret2 ^= e;}for(int i = 1; i <= nums.size()+2; i++){if( ((i >> pos) & 1) == 1)ret1 ^= i;else ret2 ^= i;}return {ret1, ret2};}
};
