优选算法的慧根之翼：位运算专题

专栏：算法的魔法世界

个人主页：手握风云

一、位运算

• 基础位运算

        共包含6种&(按位与，有0就是0)、|(按位或有1就是1)、^(按位异或，相同为0，相异为1)、~(按位取反，0变成1，1变成0)、<<(左移)、>>(右移)。

• 给定一个数n，确定它的二进制表示中第x位是0还是1

        我们先给出一个约定，以最低的一位为0位，从右向左依次递增。我们想确定第x位，只需让这一位数右移x位，再与1进行按位与操作。如果这一位是1，异或结果为1；如果这一位是0，异或结果为0。

• 将一个数n的二进制表示的第x位修改为1

        只需要将第x位修改为1，其他位不变。我们只需要将1左移x位，再与之进行按位或操作。

• 将一个数n的二进制表示的第x位修改为0

        与上面的操作思路差不多。先将1左移x位，再进行取反操作，再与之进行按位与操作。

• 位图的思想

        位图的本质还是一个哈希表，哈希表的本质又是一个数组。现在我们可以用一个整型变量的比特位01来记录这些信息。

        我们直接使用n&(-n)，而-n的求法可以先按位取反再加1。

• 干掉一个数n二进制表示的最右侧的1

        就是把最右侧的1修改为0。n & (n-1)，因为减1需要借位。

• 运算的优先级

        位运算的符号太多，记起来太复杂了。我们只需要记住能加括号加括号

• 异或运算的规律

        a ^ 0 = a；a ^ a = 0；a ^ b ^ c = a ^ (b ^ c)

二、例题讲解

2.1. 判定字符是否唯一

        第一种解法，使用哈希表。我们先遍历一遍字符串，看看这个字符在不在哈希表中，如果某个出现了两次，直接返回false。时间复杂度，空间复杂度因为创建了哈希表，

class Solution {public boolean isUnique(String astr) {boolean[] hash = new boolean[128];for (int i = 0; i < astr.length(); i++) {char c = astr.charAt(i);if(hash[c]){return false;}hash[c] = true;}return true;}
}

        解法二：位图。建立一个大小为26的位图，用0来表示未出现，1来表示出现过一次。通过不断地判断某一位是否为1和修改为1，就可以判断字符是否为1。

        我们还可以用鸽巢原理进行优化：如果字符串长度大于26，那么一定存在重复的字符。

        完整代码实现：

public 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;}
}

2.2. 丢失的数字

        解法1：创建一个大小为n+1的哈希表，利用数组元素与哈希表的下标一一对应的关系找出丢失的数字。时间复杂度和空间复杂度都为。

        解法2：高斯求和。((首项+尾项)*项数)/2 - 数组的和。时间复杂度为，空间复杂度为。

        解法3：利用异或运算的定律。我们以示例1为例，我们用原始数组与完整的数进行异或运算，最终得到的结果就为丢失的数字。

        完整代码实现：

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

2.3. 两整数之和

        解法：异或位运算，因为异或位运算还可以有另一种理解，“无进位相加”，所以说我们接下来就要实现进位就可以。如下图，按位与正好能实现这种进位。

        但我们需要注意的是，进位不是进到它本身这一位来，而是要进到左边这一位上来，所以我们还需要将按位与的结果左移1位，直到左移的结果为0。

        完整代码实现：

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;}
}

2.4. 只出现一次的数字 II

        我们假设数组中出现三次的数字有n个，只出现一次的有1个，数组里的元素都是int类型的，我们从第0位开始遍历，让每一个数相同位数的比特位相加，那么它们的相加一共可以出现如下图4种情况。我们每遍历完一位，余数为0，就将只出现一次的数字该位的比特位修改为0；余数为1，就将只出现一次的数字该位的比特位修改为1。直到遍历到最后并修改一位比特位，找出只出现一次的数字。

        我们甚至还可以拓展到如果其他数字恰好出现n次，我们也可以利用上面的思路。

        完整代码实现：

class Solution {public int singleNumber(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;}return ret;}
}

2.5. 消失的两个数字

        我们先利用完整的数与原始数组进行异或操作，最终得到的结果为两个消失的数字的异或结果。我们假设tmp = a^b，下一步，找到tmp比特位中最右边的1。因为a与b是两个不同的数字，一定会存在相同位上不同的比特位，所以tmp的比特位一定会存在一位1。然后根据比特位上的不同，划分为两类异或。

        完整代码实现：

class Solution {public int[] missingTwo(int[] nums) {//先把所有数异或在一起int tmp = 0;for (int x : nums) tmp ^= x;for (int i = 0; i <= nums.length + 2; i++) tmp ^= i;//找到a、b不同的那一位int diff = 0;while (true) {if (((tmp >> diff) & 1) == 1) break;else diff++;}//根据diff位不同，分为两类异或int[] ret = new int[2];for (int x : nums) {if (((x >> diff) & 1) == 1) ret[1] ^= x;else ret[0] ^= x;}for (int i = 0; i <= nums.length + 2; i++) {if (((i >> diff) & 1) == 1) ret[1] ^= i;else ret[0] ^= i;}return ret;}
}