【Java 优选算法】位运算

欢迎关注个人主页：逸狼

---

创造不易，可以点点赞吗~

如有错误，欢迎指出~

---

---

基础位运算符:

&: 有 0 就是 0

| : 有 1 就是 1

^ :相同为0,相异为1(无进位相加)

1.给一个数 n, 确定它的二进制表示中的第x位是 0 还是 1 . 使用公式(n >> x) & 1

2.将一个数 n 的二进制表示的 第x位 修改成 1. 将x位置 | 1,其余位置 | 0, 操作: n = n | (1 << x)

3.将一个数n 的二进制表示的第x 位修改成0. 将x位置 & 0,其余位置 & 1,操作: n = n&(~(1 << x) )

4.lowbit提取一个数(n)二进制表示中最右侧的1 . 让-n(让数n 按位取反再加1) & n

其中 -n 操作 本质是:将最左侧的1 的左边区域全部变成相反 

 

5.将一个数(n)二进制表示中的最左侧的1变成0. 使用 n & (n - 1) 

6.异或(^)运算的运算律 

1. a ^ 0 = a 
2. a ^ a = 0(消消乐)
3. a ^ b ^ c = a ^ (b ^ c)

由第一个和第二个规律延申: 奇数个a相异或得到a, 偶数个a异或得到0

对应的题目练习

判定字符是否唯一

题目链接

解法

解法一: 利用哈希表 ,遍历字符串,每次将字符放进hash表中,判断是否重复. 时间复杂度和空间复杂度都是O(n),但其实new一个hash[26]就行

解法二: 位图, 用一个int 32位中的0~25位每一位表示26个字母,0代表没出现过,1代表出现了

优化:鸽巢原理(抽屉原理),如果字符串长度大于26个,那么一定是有重复的字母

代码

class Solution {public boolean isUnique(String astr) {//优化if(astr.length() > 26) return false;int bitMap = 0;for(int i = 1; i < astr.length(); i++){int x = astr.charAt(i) - 'a';//先判断字符是否在位图中if((bitMap >> x) & 1 == 1) return false;//把当前字符加入位图中bitMap |= 1 << x;}return true;   }
}

丢失的数字

题目链接

解法

解法一: 哈希集合,遍历数组,将出现的过的数字标记为1

解法二: 高斯求和, 求0到5的和 ,再减去nums的和,得出结果

 解法三: 异或运算规律, 将nums和0到5的所有数字都 异或 ,得到的结果就是 消失的数字

代码

//利用哈希集合
class Solution {public int missingNumber(int[] nums) {//利用集合Set<Integer> set = new HashSet<>();int n = nums.length;//先把原数组放到set里for(int x : nums) set.add(x);int ret = -1;//把完整数组的每一个元素放到set里判断是否包含,即可查出缺失的数字for(int i = 0; i <= n; i++){if(!set.contains(i)){ret = i;break;}}return ret;}
}//利用高斯求和
class Solution {public int missingNumber(int[] nums) {int n = nums.length;int ret = (n * (n + 1)) / 2;for(int i : nums) ret -= i;return ret;}
}//利用异或
class Solution {public int missingNumber(int[] nums) {int ret = 0;for(int x : nums){ret ^= x;}        for(int i = 0; i <= nums.length; i++){ret ^= i;           }return ret;}
}

两整数之和

题目链接

解法

利用位运算, 将要计算的两个数的和拆分为 两部分: 无进位和 以及 进位和 

1. 无进位相加 ,"异或"运算:, 即a ^ b,
2. 进位操作可以使用 "与"运算后再左移一位用符号表示: (a & b) << 1

步骤1得到的数又重新记为 a, 步骤2得到得到的数重新记为b,重复以上操作,最后直到b=0即可得出结果

画图举例

代码

class Solution {public int getSum(int a, int b) {while(b != 0){int tmp = a;a ^= b;//先算出无进位相加b = (b & tmp)<<1;//算出进位相加}return a;}
}

只出现一次的数字||

题目链接

解法

题目要求实现: 线性时间复杂度 即O(n),常数级空间复杂度 即O(n)

 数组中所有数的比特位 相加可以分为4种情况,如下图

将每一个数的 每一位比特位分别对应相加 后 再%3得到的就是 只出现过一次的数a

画图举例

代码

class Solution {public int singleNumber(int[] nums) {int ret = 0;for(int i = 0; i < 32; i++){//依次修改ret中的每一个比特位int sum = 0;//统计nums中所有数的第i为的和for(int x : nums){if(((x >> i) & 1) == 1){sum++;}} sum %= 3;//超时sum对应i位置ret中比特位的数,//如果sum是1,就将ret的i位置修改为1,0则不用管if(sum == 1) ret |= 1 << i;}return ret;}
}

消失的两个数字

题目链接

解法 

将nums 和 完整数组1~n的所有数字都异或 得到的结果就是a^b(必定不为0),结果就是将a^b分开得到a和b,问题就转变成了: 已知a^b,如何将a和b分开

找到a^b相异的部分dif(即a^b的比特位第一次出现1的位置),将所有的数通过 dif 分类开,再 异或,就可以得到a和b

代码

class Solution {public int[] missingTwo(int[] nums) {int tmp = 0;for(int x: nums) tmp ^= x;for(int i = 1;i <= nums.length + 2;i++) tmp ^= i;//找出a,b两个数比特位不同的第一位,即第一次出现1的位置int dif= 0;while(true){if(((tmp >> dif) & 1) == 1) break;else dif++;}int[] ret = new int[2];for(int x: nums){if(((x >> dif) & 1) == 1) ret[1] ^= x;else ret[0] ^= x; }//将所有的数按照dif位不同,分两类进行异或for(int i =1 ;i <= nums.length + 2;i++){if(((i >> dif) & 1) == 1) ret[1] ^= i;else ret[0] ^= i;}return ret;}
}