【笑着写算法系列】位运算

前言

位运算可以说是一个算法里面比较神奇的算法，利用这个算法可以用极少的资源来完成一些运算，主要得力于位运算的一些特殊的性质。

在进行题目练习之前我们先了解一下有关位运算的一些主要作用:

确定一个数n的第x位二进制位是0还是1,我们可以使用(（n>>x）&1))==1,来进行判断。将一个数n的第x位二进制 改成1,n=n|(1<<x)将一个数n的第x位二进制改成0，n=n&（~(1<<x)）提取一个数n二进制位中最右侧的1，n&(-n)干掉一个数n二进制位中最右侧的1，n&（n-1）0^n=n；n^n=0;a^b^c=a^(b^c);

位图的使用： 什么是位图呢，你可以理解为将一个数的二级制位如：int n。我们可以用n的32个二进制位来进行信息的存储。比如这个二进制位为1代表一个数出现过，0代表这个数没有出现过。类似于一种简单的hash表。

一、丢失的数字

参考答案及其解析：\

既然我们这篇文章设计位运算，那么我就讲解如何利用位运算进行快速解决这个问题。

我们就借助位运算中"^"这个异或运算符，首先我们要直到异或的两个特殊情况，

0^n=n；

n^n=0;

且a^b^c=a^(b^c);

就是上面这两个特殊情况就可以让我们很快的解决这个问题，因为再[0,n]的范围内缺少了一个数，那么我们先是把数组中所有的数进行异或，然后顺便把0-n中的每个数也进行异或，这样除了那个缺失的数，其余的每个数相互异或=0，只剩一个缺失的数x^0=x,我们只需要返回这个数即可。

class Solution { public int missingNumber(int[] nums) { int n=nums.length; int ret=0; int i=0; for(i=0;i<n;i++){ ret^=nums[i]^i; } return ret^i; } }

二、判定字符是否唯一

参考答案及其解析：

这里我们运用到“位图”，即：我们可以使用一个基本类型的每个比特位（也就是每个二进制位）模拟成一个简单的hash表，这样我们就可以减少空间复杂度，例如：题目中说只要存在重复的字母就返回false，否则返回true，那么我们就像是模范hash表，只要字母出现过我们就tmp中的对应的位改成1，每次循环检查当前字母对应的位数为1的话，我们就直接返回false。

优化：鸽巢原理进行优化，即：题目告诉我们只有小写字母，那么只要这个字符串astr的长度超过26个，就一定会有重复的字母。

class Solution { public boolean isUnique(String astr) { if(astr.length()>26) return false; int tmp=0; int c; for(int i=0;i<astr.length();i++){ c=astr.charAt(i); if((tmp>>(c-'a')&1)==1) return false; else tmp=tmp|(1<<c-'a'); } return true; } }

三、两整数之和（不是要+号）

参考代码及其解析：

我们要知道异或这个操作也可以被称为无进位相加。那么我们想要实现真正的相加且不用+号，那么我们就必须要找到对应的进位，然后再进行相加（不断循环），直到这个进位为carry=0；如下代码：我们先是计算当前进位carry。然后进行异或（无进位相加）然后再继续循环相加，直到没有进位为0。

class Solution { public int getSum(int a, int b) { while (b != 0) { int carry = (a & b) << 1; a = a ^ b; b = carry; } return a; } } 四、只出现一次的数字

参考代码及其解析：

首先题目告诉我们数组除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。那么我们就按照整型的32个二进制位来进行操作，因为我们要排除掉出现三次的元素，只留下出现一次的元素，这时我们可以计算每个位中1的个数然后进行%3取模操作，这样我们就可以将三个相同的数的位数除去，只剩下出现一次的数决定那个位数。

class Solution4 { public int singleNumber(int[] nums) { int ret=0; for(int i=0;i<32;i++){ int n=0; for(int j=0;j<nums.length;j++){ n+=(nums[j]>>i)&1; } if(n%3!=0) ret|=1<<i; } return ret; } }

五、消失的两个数字

参考代码及其解析：

根据题目我们先是将数组中所有的值和1-N的所有值进行异或，这时得到的值就是那两个缺失的数字异或的值tmp，那么这时我们就可以根据这个异或得到的值将我们数组中的值和1-N分成两类，如何分呢？

首先我们根据得到的tmp值随便找出一位其中一个为1的二进制位，然后根据这个二进制是否为1对数组中的值和1-N分成两类，然后分别异或，得到的两个值就是缺失的那两个数了。

因为那个二进制位为1说明缺失的a和b这两个数这个二进制肯定是不同的，根据这个分类就不会把a和b分到同一类了。

class Solution { public int[] missingTwo(int[] nums) { int n=nums.length; int tmp=nums[0]; int[] ret=new int[2]; for(int i=1;i<n;i++){ tmp^=i^nums[i]; } tmp^=(n+2)^(n+1)^n; int i=0; for(i=0;i<32;i++){ if(((tmp>>i)&1)==1) break; } for(int num:nums){ if(((num>>i)&1)==1) ret[0]^=num; else ret[1]^=num; } for(int j=1;j<=n+2;j++){ if(((j>>i)&1)==1) ret[0]^=j; else ret[1]^=j; } return ret; } }