位运算算法基础与经典例题解析

将数 n 取反后 +1 得到相反数 -n，然后两数按位与 & 得到最右侧的 1。即最右侧的 1 及其右边都不变，左边的数都变成 0。

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

将数 n 减 1，然后两数按位与 & 干掉最右侧的 1。即最右侧的 1 及其右边都变成 0，左边的数都不变。

1.8 位运算的优先级

通常优先级为：~ > & > ^ > | 但是记起来太麻烦了，干脆直接加括号更好。

1.9 异或运算符 ^ 的运算律

这是异或运算符^常用的运算律，在题目中经常用。

2. 判定字符是否唯一

题目描述：

示例：

参考链接：判定字符是否唯一

题解:

通常统计多数的字母出现次数一般想到的是哈希表，时间空间复杂度都为 O(n)，这就有人问了，有没有既简单又强势的方法能够解决？有的兄弟有的，这么强势的方法有九个，因为本题只涉及 26 个小写英文字母，所以可以用减少开辟空间的位图。

如上述介绍位图一样，用 1 和 0 表示字母是否出现过，如果为 1，就返回 false；如果是 0，就添加 1 到指定位数上，遍历完字符串后返回 true。

细节问题:

利用鸽巢原理，如果字符串长度大于 26，那么必定有字母是重复的，所以大于 26 直接返回 false。

代码实现:

#include <iostream>
#include <string>
using namespace std;

class Solution {
public:
    bool isUnique(string astr) {
        if (astr.size() > 26) {
            return false;
        }
        int bitMap = 0;
        for (auto ch : astr) {
            int i = ch - 'a';
            if ((bitMap >> i) & 1 == 1) {
                return false;
            }
            bitMap |= 1 << i;
        }
        return true;
    }
};

3. 丢失的数字

题目描述：

示例：

参考链接：丢失的数字

题解:

该题一共有四种方法解决。

哈希表

把 0 ~ n 中出现的所有数字都放进哈希表里，然后遍历一遍哈希表，如果某一格内对应的 0，那么该数就是缺失的数字。

高斯求和

利用简单的求和公式求出 0 ~ n 所有数的和，然后减去缺失数字的数组，剩下的数就是题意所求。

二分查找

先对数组进行排序，在连续数组的前提下，缺失数字的位置开始下标与实际值不同，很明显二段性立马就出来了，如果在右区间，那么 mid 会有等于缺失值的实际位置索引，即 right = mid；如果在左区间，mid 及其前面的值都不可能是缺失值的实际位置索引，即 left = mid + 1。

位运算

根据异或运算^的运算律，相同的两个数异或会抵消成 0，所以显而易见，把缺失数字的数组和完整的数组异或，剩下的就是缺失的数字。

代码实现:

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int ret = 0;
        for (auto x : nums) {
            ret ^= x;
        }
        for (int i = 0; i <= nums.size(); ++i) {
            ret ^= i;
        }
        return ret;
    }
};

4. 两整数之和

题目描述：

示例：

参考链接：两整数之和

题解:

很显然本题是一道为了笔试而出题的题，通常是不会要我们这样去计算的，如果是在笔试环节时，可以投机取巧，直接 return a+b 通过测试用例，一般面试官也不会去看你的代码。

言归正传，该题主要使用异或运算 + 无进位相加解决。

我们知道无进位相加就是只相加不进位，所以我们只要解决了进位问题，那么问题就迎刃而解了，那么进位也只会在两个位都为 1 的情况下才会进位，观察发现进位的操作就是按位与&，注意要进位的是下一位，所以要把按位与&完的结果右移一位。两个结果不断重复上述操作，直到进位为 0，就是相加的最终结果。

细节问题:

注意进位的数有可能因为一直右移导致为 -1，只要强转为无符号整数就行。

代码实现:

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int getSum(int a, int b) {
        while (b != 0) {
            int x = a ^ b;
            unsigned int carry = (unsigned int)(a & b) << 1;
            a = x;
            b = carry;
        }
        return a;
    }
};

5. 只出现一次的数字Ⅱ

题目描述：

示例：

参考链接：只出现一次的数字Ⅱ

题解:

本题的解法是一种通用解法，以后遇到类似的题目思路是一样的，但是前提是要见过这种解法，这种思路十分的巧妙。

因为除去单独的数，每个数的一位必定出现三次，也就是三的倍数。

所以每个数的指定位数之和必定为如图四种情况的一种，对加和总数求余数发现剩下的数就是那个单独的数的指定位数，很好，如此一来就发现了规律，如此循环往复，把每一位存入位图就能求出只出现一次的数。

细节问题:

实际上本题还能改成出现 n 次，只要把求余数时改成除 n 就行，其余的算法思路是一样的。

代码实现:

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        for (int i = 0; i < 32; ++i) {
            int sum = 0;
            for (auto x : nums) {
                if (((x >> i) & 1) == 1) {
                    sum++;
                }
            }
            sum %= 3;
            if (sum == 1) {
                ret |= 1 << i;
            }
        }
        return ret;
    }
};

6. 消失的两个数字

题目描述：

示例：

参考链接：消失的两个数字

题解:

本题是丢失的数字的延伸扩展，难度可以说是上升不少，掌握了这题以后无论是丢失了几个数字都可以用相同的思路来做。

第一步：

显而易见，首先利用异或的特性把 nums 和完整数组异或，得到缺失的两个数的异或结果，即 a ^ b。

第二步：

接下来是最关键的一步，我们要知道除了 a、b 以外的数在异或时是偶数个，所以能够相互抵消，已知 a ^ b = 1，所以两个数异或后为 1 的那一位，表示在这一位上两个数必然不同，一个数为 1，另一个数为 0。那么我们就可以根据这个差异，异或后为 1 有很多位，我们选取最右侧的 1 来分组方便计算。

基于此，我们把最右侧的 1 这一位定为 diff，先把 nums 进行分类，如果 nums 在 diff 位是 1，那么就和 a 异或^；如果 nums 在 diff 位是 0，那么就和 b 异或^。那么我们现在就是把有差异的那一位和 nums 异或并分类了，所以我们还要和一个完整的数组分类异或，抵消掉别的数，因为相同异或为 0，不同异或为 1，由于前面的分类，除了丢失的数，其他的数都抵消了，丢失的数也在异或的过程中把剩余位数补上了。

代码实现:

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int ret = 0;
        for (auto x : nums) {
            ret ^= x;
        }
        for (int i = 1; i <= nums.size() + 2; ++i) {
            ret ^= i;
        }
        int diff = 0;
        while (1) {
            if (((ret >> diff) & 1) == 1) {
                break;
            } else {
                diff++;
            }
        }
        int a = 0, b = 0;
        for (auto x : nums) {
            if (((x >> diff) & 1) == 1) {
                b ^= x;
            } else {
                a ^= x;
            }
        }
        for (int i = 1; i <= nums.size() + 2; ++i) {
            if (((i >> diff) & 1) == 1) {
                b ^= i;
            } else {
                a ^= i;
            }
        }
        return {a, b};
    }
};