算法日记专题：位运算I（汉明距离I II 面试题：判断是不是唯一的字符 丢失的数字 两个整数相加）

🎬 胖咕噜的稞达鸭：个人主页

🐥位运算常见总结：

本专题后缀文章：

算法日记专题：位运算II（ 只出现一次的数字I II III 面试题：消失的两个数字 比特位计数）

461.汉明距离

汉明距离力扣链接

题解：这两个数字对应二进制位不同的位置的数目。
解题思路:先异或，求出异或和，异或（相同为0，相异为1）。所以汉明距离本质上找的就是汉明距离 = 两个数异或结果的二进制表示中 1 的个数。

方法一：求异或和ret二进制表达中每一位数字是否为1，如果是1就加起来；

classSolution{public:inthammingDistance(intx,inty){intret=x^y;//求出异或和intcount=0;//x和y中不同位置的数字到底有几个while(ret!=0)//从异或和的最低位开始依次看{count+=ret&1;//如果二进制位1，就加到count中ret>>=1;//右移一位}returncount;}};

方法二:汉明距离的实质：找出一个数字二进制表达中1的个数
本题中，这个数字就是x和y的异或和。

classSolution{public:inthammingDistance(intx,inty){intsum=x^y;//求出异或和//以下就是在找一个二进制数字中有多少个1intret=0;for(inti=0;i<32;i++){if(sum>>i&1)ret++;}returnret;}};

方法三：
使用内置函数：

classSolution{public:inthammingDistance(intx,inty){bitset<32>bits(x^y);//bitset<32>：C++中的一个模板类，表示固定大小的二进制位集合（这里设为32位）intsum=bits.count();//返回不同的位置有几个returnsum;}};

477.汉明距离总和

汉明距离总和力扣链接

解法一：暴力求解（会超时，但是可以通过该题，用来锻炼对位运算这类题型的熟悉程度）
汉明距离的实质上是在求一个数字二进制表达中1的个数。
所以我们将数组中的数字两两异或，求出不同位置的1，最后将所有1都集合在一起返回个数即为所求。

有个问题：如果数组中出现重复的数字，重复的两个数字异或一定是0，会严重影响最后的统计结果，
所以在i 和 j 的选取时，有个细节，i 可以从0开始，但是j 要从 i+1 开始，这是一个简单的数学题：
如果for(int i = 0;i < nums.size();i++)
for(int j = 1; j < nums.size();j++)，很显然出现重复数字。
i = 0 : j = 1 , 2 , 3 → ( 0 , 1 ) , ( 0 , 2 ) , ( 0 , 3 ) ✓ i=0: j=1,2,3 → (0,1), (0,2), (0,3) ✓i=0:j=1,2,3→(0,1),(0,2),(0,3)✓
i = 1 : j = 1 , 2 , 3 → ( 1 , 1 ) , ( 1 , 2 ) , ( 1 , 3 ) i=1: j=1,2,3 → (1,1), (1,2), (1,3)i=1:j=1,2,3→(1,1),(1,2),(1,3)
i = 2 : j = 1 , 2 , 3 → ( 2 , 1 ) , ( 2 , 2 ) , ( 2 , 3 ) i=2: j=1,2,3 → (2,1), (2,2), (2,3)i=2:j=1,2,3→(2,1),(2,2),(2,3)
i = 3 : j = 1 , 2 , 3 → ( 3 , 1 ) , ( 3 , 2 ) , ( 3 , 3 ) i=3: j=1,2,3 → (3,1), (3,2), (3,3)i=3:j=1,2,3→(3,1),(3,2),(3,3)
所以j的起始位置：for(int j = 1+i; j < nums.size();j++)可以理解为去重操作。

classSolution{public:inttotalHammingDistance(vector<int>&nums){intret=0;//用于返回最后的总和for(inti=0;i<nums.size();i++){for(intj=1+i;j<nums.size();j++){intdiff=nums[i]^nums[j];// 计算diff中1的个数while(diff)//循环成立的条件是diff == 1{ret++;//不断将每一位的1加入到ret中diff&=diff-1;// 清除最低位的1}}}returnret;}};classSolution{public:inttotalHammingDistance(vector<int>&nums){intsum=0;for(inti=0;i<nums.size();i++){for(intj=1+i;j<nums.size();j++){intdiff=nums[i]^nums[j];// 计算diff中1的个数for(inti=0;i<32;i++){if((diff>>i)&1)sum++;}}}returnsum;}};

解法二：用内置函数

classSolution{public:inttotalHammingDistance(vector<int>&nums){intn=nums.size();//这道题就是找多个数二进制数字两两对比不一样的位置，最终求出总和inttotal=0;for(inti=0;i<n;i++)//外层循环 i：选择第一个数{for(intj=i+1;j<n;j++)//内层循环 j = i+1：选择第二个数total+=std::bitset<32>(nums[i]^nums[j]).count();//从 i+1 开始，避免重复计算(a,b)和(b,a)，也避免计算(a,a)（距离为0）}returntotal;}};

解法三：
对于二进制每一位，汉明距离的总贡献 = (该位为1的数字个数) × (该位为0的数字个数)，就是说对于一个二进制位数字，有count位是1，有n - count是0

classSolution{public:inttotalHammingDistance(vector<int>&nums){intn=nums.size();intret=0;for(inti=0;i<32;i++){intcount=0;for(intnum:nums)//遍历数组中的每一个数{if((num>>i)&1)count++;//将二进制表示中的1加到count中}ret+=count*(n-count);//对于二进制每一位，汉明距离的总贡献 = (该位为1的数字个数) × (该位为0的数字个数)，就是说对于一个二进制位数字，有count位是1，有n - count是0}returnret;}};

代码实现原理：

nums = [4, 14, 2] = [0100, 1110, 0010]
n = 3
第0位：所有数都是0 → count=0 → 贡献=0×3=0
第1位：14(1), 2(1), 4(0) → count=2 → 贡献=2×1=2
第2位：4(1), 14(1), 2(0) → count=2 → 贡献=2×1=2
第3位：14(1), 4(0), 2(0) → count=1 → 贡献=1×2=2
总和 = 0 + 2 + 2 + 2 = 6

面试题：判断是不是唯一的字符

判断是不是唯一字符力扣链接

解法一：借助哈希表，将遍历到的数字丢进哈希表，如果有重复的字符就说明不是唯一的字符。仅仅需要创建一个大小为26的数组。
解法二：可以用一个比特位来标记每一个位置的下标，可以用位图的思想，32个比特位，0表示从来都没有出现过，1表示出现过一次。

解法二解题原理：判断数组中是否有重复的字符，如果有就不是唯一的字符。
将数组中的字符转换为数字，将数组中的每一个数字都遍历到位图中，进入位图时要判断这个位置是不是已经被标记为1（判断第n位的数字是0还是1）—> (n & i)，如果等于1说明是重复的字符，不等于1就标记为1（把第n位置的数字0修改为1）

优化法：鸽巢原理（抽屉原理）只有26个英文字母，但是字符的长度超过了26，就可以确定一定有一个字符出现的次数超过了1次。

解题思维：
创建一个位图，共有32位，用x进行遍历，加入位图的时候要判断此时的i是否在之前出现过，
bitMap 中没有出现过1次的i会被标记为1，
如果当前i为1，说明之前出现过了，所以不满足唯一字符的条件，返回false;（判断方法：
第i位置的数字是0还是1—>（1&(i >> bitMap )
如果当前i为0，说明之前没有出现过，就要将当前i的位置数字由0改为1；(==标记方法：
将i位置的数字由0修改为1—>((1 << i) | bitMap)==

不断在内部循环，一直到遍历完整个astr字符。

classSolution{public:boolisUnique(string astr){//利用鸽巢原理做优化if(astr.size()>26)returnfalse;//创建一个位图intbitMap=0;for(autox:astr){inti=x-'a';//先判断字符是不是之前出现过:判断第i位的数字是0还是1if((bitMap>>i)&1)returnfalse;//把当前字符加入到位图中：将第i位的数字修改为1bitMap|=1<<i;}returntrue;}};

丢失的数字

丢失的数字力扣链接

思路

方法一：排序使得数组中的元素都是有序的，遍历时发现某个数字和其索引值不同就说明这个值是丢失的数字；
方法二：高斯求和
方法三：位图思想（运行不过去，但是可以用来熟悉位运算）：进入位图，将该位置的标记由0改为1；再次遍历的时候，判断该位置的标记是1还是0，如果是0就说明没有被标记过，—>没有出现过，所以返回改位置的索引
方法四：异或，a^0=a,aa=0.将数组中所有的元素都与0异或，再将[0,nums.size()]中所有的元素与0异或，最终返回丢失数字的下标。

classSolution{public:intmissingNumber(vector<int>&nums){//方法一：sort(nums.begin(),nums.end());//排序，使数组中的数字都是有序的for(inti=0;i<nums.size();i++){if(nums[i]!=i)returni;//排序之后发现数组中有一个数字跟其索引值不一样就是丢失的数字}returnnums.size();//如果遍历的数字都在数组中，就返回不在数组中的下一个数字}};

classSolution{public:intmissingNumber(vector<int>&nums){//方法二：intsum=0;intret=0;for(inti=0;i<=nums.size();i++)ret+=i;//求出所有索引值的和for(inti=0;i<nums.size();i++){sum+=nums[i];//求出数组中存在的所有数字的和}returnret-sum;//相减得到最终的结果}};

方法三：位图的思想（不提倡，只适合32个元素的数组，本道题没有规定32个元素之内，所以位图的做法会报错）

classSolution{intmissingNumber(vector<int>&nums){//用位图的思想，判断第i位是1还是0：(i >> bitMap)&1//存入位图的时候将该位置的0修改为1 ---> bitMap |= (1 << i)longlongbitMap=0;for(intx:nums){bitMap|=(1<<x);//标记为1}for(intj=0;j<=nums.size();j++){if((bitMap&(1<<j))==0)returnj;//判断第i位是1还是0：(i >> bitMap)&1//最终返回位图标记为0的}returnnums.size();}};

但是这个做法只适合于数组中存放的元素<=32位的，最后提交的时候会报错！不提倡用位图的思想！

classSolution{public:intmissingNumber(vector<int>&nums){//方法四：异或intsum=0;for(intnum:nums)sum^=num;for(inti=0;i<=nums.size();i++)sum^=i;returnsum;}};

两个整数相加

力扣链接

classSolution{public:while(b!=0)//当还有进位的时候继续{intc=(a&b)<<1;// 计算进位a^=b;// 无进位相加b=c;// 将进位作为下一轮的加数}returna;}};classSolution{public:intgetSum(inta,intb){while(b!=0)//当还有进位的时候继续{intx=a^b;// 无进位相加unsignedintc=(unsignedint)(a&b)<<1;// 计算进位a=x;b=c;// 将进位作为下一轮的加数}returna;}};