基础算法（5）——位运算
1. 常见位运算总结
1) 基础位运算
2) 给一个数 n，确定它的二进制表示中的第 x 位是 0 还是 1
3) 将一个数 n 的二进制表示的第 x 位修改成 1
4) 将一个数 n 的二进制表示的第 x 位修改成 0
5) 位图的思想
位图的本质就是 哈希表
6) 提取一个数 n 二进制表示中最右侧的 1（lowbit）
7) 干掉一个数 n 二进制表示中最右侧的 1
例题：
191. 位1的个数 - 力扣（LeetCode）
338. 比特位计数 - 力扣（LeetCode）
461. 汉明距离 - 力扣（LeetCode）
8) 位运算的优先级
位运算符太多了，容易记混，所以不记了，能加括号就加括号
9) 异或（^）运算的运算律
例题：
136. 只出现一次的数字 - 力扣（LeetCode）
2. 判定字符是否唯一
题目描述：
解法一：数组模拟哈希表
代码实现：
class Solution {public boolean isUnique(String astr) {int n = astr.length();if (n > 26) return false; //字符串仅包含小写字母char[] arr = astr.toCharArray();int[] ret = new int[26];for (int i = 0; i < n; i++) {ret[arr[i] - 'a']++;if (ret[arr[i] - 'a'] > 1) {return false;}}return true;}
}解法二：位图
代码实现：
class Solution {public boolean isUnique(String astr) {//鸽巢原理优化if (astr.length() > 26) return false;int bitMap = 0;for (int i = 0; i < astr.length(); i++) {int x = astr.charAt(i) - 'a';//判断字符是否已存在位图中if (((bitMap >> x) & 1) == 1) return false;//将当前字符加入到位图bitMap |= 1 << x;}return true;}
}3. 丢失的数字
题目描述：
解法一：哈希表
//哈希表
class Solution {public int missingNumber(int[] nums) {int n = nums.length;int[] hash = new int[n + 1];for (int i = 0; i < n; i++) {hash[nums[i]]++;}for (int i = 0; i < hash.length; i++) {if (hash[i] == 0) {return i;}}return -1;}
}解法二：高斯求和
//高斯求和
class Solution {public int missingNumber(int[] nums) {int n = nums.length;int sum1 = 0;int sum2 = 0;for (int i = 0; i < n; i++) {sum1 += nums[i];}for (int i = 0; i <= n; i++) {sum2 += i;}return sum2 - sum1;}
}解法三：位运算（异或运算的运算律）
//位运算
class Solution {public int missingNumber(int[] nums) {int n = nums.length;int ret = 0;for (int i = 0; i < n; i ++) {ret ^= nums[i];}for (int i = 0; i <= n; i++) {ret ^= i;}return ret;}
}4. 两整数之和
题目描述：
解法：位运算（异或运算 - 无进位相加）
算法思路：
代码实现：
class Solution {public int getSum(int a, int b) {while (b != 0) {int x = a ^ b; // 计算无进位相加的结果int y = (a & b) << 1; // 计算进位a = x;b = y;}return a;}
}5. 只出现一次的数字 II
题目描述：
解法：利用位运算依次确定每一个二进制位
代码实现：
class Solution {public int singleNumber(int[] nums) {int ret = 0;for (int i = 0; i < 32; i++) { // 依次修改 ret 中的每一个比特位int sum = 0;for (int x : nums) { // 统计 nums 中所有的数的第 i 位二进制的和if (((x >> i) & 1) == 1) {sum++;}}sum %= 3;if (sum == 1) ret |= (1 << i); // 将ret 的第 i 位二进制修改为 1}return ret;}
}6. 只出现一次的数字III
题目描述：
算法思路：
是下面 7 题的思路的一部分
代码实现：
class Solution {public int[] singleNumber(int[] nums) {// 1. 找到 a ^ bint tmp = 0;for (int x : nums) {tmp ^= x;}// 2. 找到 tmp 二进制位中最右侧为 1 的位置int diff = 0;while (true) {if (((tmp >> diff) & 1) == 1) {break;}diff++;}// 3. 按照 diff 位置为1或0，将数组分为两类分别异或int[] ret = new int[2];for (int x : nums) {if (((x >> diff) & 1) == 1) {ret[0] ^= x;} else {ret[1] ^= x;}}return ret;}
}7. 消失的两个数字
题目描述：
算法思路：
结合 268. 丢失的数字 和 260. 只出现一次的数字 III 两题
代码实现：
class Solution {public int[] missingTwo(int[] nums) {int n = nums.length;// 1. 先把所有数异或在一起int tmp = nums[0];for (int i = 1; i < n; i++) {tmp ^= nums[i];}for (int i = 0; i <= n + 2; i++) { // 注：此处为 <=tmp ^= i;}// 2. 找到 a,b 两个数比特位不同的位置int x = -1; // 使用 x 记录该位置for (int i = 0; i < 32; i++) {if (((tmp >> i) & 1) == 1) {x = i;break;}}// 3. 将所有的数按照 x 位置是0还是1，分为两类异或int[] ret = new int[2];for (int i : nums) {if (((i >> x) & 1) == 1) ret[0] ^= i;else ret[1] ^= i;}for (int i = 1; i <= n + 2; i++) {if (((i >> x) & 1) == 1) ret[0] ^= i;else ret[1] ^= i;}return ret;}
}