位运算应用 经典题目

思路都被折叠起来了，可以在看完题目之后想一想，实在想不出再看思路捏 虽然一般看原链接的题解就行了

部分可用的 位运算常用知识（不解释原理，如果需要解释原理的话直接在评论区滴滴我）：

lowbit运算 —— 用于 求出一个数字的二进制形式 最低位的1，并搞成一个数字

如 lowbit(44)，先有 44的二进制形式00101100，然后我们可以知道 最低位是第 2 位（从右往左数，并从0开始数），则lowbit(44) = 00000100，即 lowbit(44) = 4，这个数字就是lowbit(44)的结果

lowbit运算的公式：lowbit(n) = n & (~n + 1) = n & -n

1、异或的 位信息累积 性质

相信大家都接触过 无中间变量交换两个数 这种题目吧？

没有吗？那我简单提一提罢（

一般我们交换两个数是这样操作的：

int a = 10, b = 20, tmp;
tmp = a; a = b; b = tmp;//运用了中间变量

但还有这样的：

int a = 10, b = 20; 
a = a + b; b = a - b; a = a - b;

能看懂为什么这个东西能这么交换吗？

其实就是因为a = a + b 时，我们将 a的信息和b的信息 累积到a这个空间里，使得 a这个空间能够存两份数据，而此时b的空间内存的值并没有改变，因此b能帮助我们从处理过后的a中 解码出原先的a值 —— 以 a - b 的形式得到原先的a值；

这么一说是不是就很清晰了呢？

那异或运算也是同理，也能有这样的操作：

int a = 10, b = 20;
a = a ^ b; b = a ^ b; a = a ^ b;

说是同理，是因为 异或 能累积两个数中的位的有效信息，这里的 位的有效信息 指的就是 两个数字有哪些位相同，哪些位不相同；当然，b空间存放的数化成二进制后 也同样能从 被处理过的a中 解码出原先的a值 —— 用 a ^ b 的方式。

所以，我们能发现 —— 异或运算 能够累积两个数中的位的有效信息 这一点，就足够我们在很多地方用到它了！！

2、异或的 同假异真 性质

136. 只出现一次的数字 - 力扣（LeetCode）

思路：

异或运算，就是 相同二进制上 如果数码相同，则 运算得到0；如果相同二进制位上的数码不同，则 运算得到1；

如：

​ 对 00001010(10) 和 00001111(15) 进行异或运算（C++代码写为10 ^ 15），最终得到 00000101(5)；

而我们很容易发现，如果进行异或运算的数字 是同一个的话，那他们的二进制位形式完全相同，因而它们的异或结果就一定会是 0 —— 以此性质，我们就能确认两个数是否相同，也可以借助这个性质，将 相同的两个数 通过 异或运算 消除掉。

//AC代码
class Solution {
public:
    int singleNumber(vector<int>& nums) 
    {
        int ans = 0;
        for(int i = 0; i < nums.size(); i++)
            ans ^= nums[i];
        return ans;
    }
};

260. 只出现一次的数字 III - 力扣（LeetCode）

基于上一题，我们可以得到 异或能用来消去相同数字 这一应用，但是对于这道 存在两个不同数字 的异或累积……我们要怎么做嘞？

思路：

当然还是 先求全体数字的异或累积 辣！！

然后你就能得到 一个将两个不同的数字 a，b 异或在一起的最终结果res

但是要怎么将这两个数从res中分离开嘞？？

只需要找到res内任意一个是 1 的二进制位，这个 1 表示的含义就是：a和b这两个数 在这个位上 不相同。这个位可以用lowbit运算来找 最方便。

我们因此可以依据 这个不相同的位k上的数码是否相同 来对 原来的数据进行分类 —— 这样就能保证 a和b在不同的分类上了，因为这俩在这个位上的数码 必不相同。

而其他的数字又必有一个完全相同的数字，且 这两个完全相同的数字 也必会被归类到同一个分类里，故对两个分类各自求异或累积，结果就能得到 两个数，这两个数就是a和b捏~

//AC代码
class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) 
    {
        int n = nums.size(), tmp = nums[0];
        for(int i = 1; i < n; i++) tmp ^= nums[i];
        
        //int spedigit = tmp & (-tmp);
        int spedigit = tmp == INT_MIN ? 1 : tmp & (-tmp);//防止溢出
        int tmp1 = 0, tmp2 = 0;
        for(int i = 0; i < n; i++)
        {
            if(nums[i] & spedigit) tmp1 ^= nums[i];
            else tmp2 ^= nums[i];
        }
        return {tmp1, tmp2};
    }
};

关于防止溢出 这个点，这里不多讲，因为跟 计算机存储数字的方式有关，但是必须得会，不然没法玩转 位运算

欢迎各位大佬批评（轻喷）