当前位置：首页 > article >正文

位运算算法

article 2024/11/24 14:27:19

基本位运算符

1.基本位运算

1.1.位运算符的优先级

1.2.给一个数n，确定它的二进制表示中的第x位是0还是1（按位与）

1.3.将一个数n的二进制表示的第x位修改成1（按位或）

1.4.将一个数n的二进制表示的第x位修改成0

1.5.提取一个数n二进制表示中最右侧的1

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

1.7.异或（^）运算的运算律

2.小练习

题目一——191. 位1的个数 - 力扣（LeetCode）

题目二——338. 比特位计数 - 力扣（LeetCode）

题目三——461. 汉明距离 - 力扣（LeetCode）

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

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

3.大练习

3.1.题目六——面试题 01.01. 判定字符是否唯一 - 力扣（LeetCode）

3.1.1.哈希表解法（unordered_map模拟）

3.1.2.位图解法

3.2.题目七——268. 丢失的数字 - 力扣（LeetCode）

3.2.1.哈希表解法（unordered_map模拟）

3.2.2.高斯求和公式

3.2.3. 异或解法

3.3.题目八—— 371. 两整数之和 - 力扣（LeetCode）

3.3.1.面试解法

3.3.2.异或用于加法运算

3.4.题目九——137. 只出现一次的数字 II - 力扣（LeetCode）

3.4.1.哈希表（unordered_map模拟）

3.4.2.位运算解法

3.5.题目十——面试题 17.19. 消失的两个数字 - 力扣（LeetCode）编辑

3.5.1.位运算解法

基本位运算符

首先我们要讲清楚我们的最基本的运算符

<<
>>
~
按位与&（有0就是0）
按位或|（有1就是1）
按位异或^（相同为0，相异为1 / 无进位相加）

如果不清楚的可以去：C++原码，反码，补码，位运算符(＜＜，＞＞，|，^，&）_c++补码-CSDN博客

1.基本位运算

1.1.位运算符的优先级

我们不管位运算符的优先级，我们先仔细看下面这个例子

例如，考虑以下表达式：

int result = a << b & c;

在这个表达式中，按位左移运算符<<的优先级高于按位与运算符&，所以表达式实际上等价于：

int result = (a << b) & c;

但是，如果我们的意图是先进行按位与操作，然后再进行按位左移，那么我们就需要使用括号来明确这一点：

int result = a << (b & c);

在这个修改后的表达式中，括号内的按位与操作会首先执行，然后结果再进行按位左移。

总之就一句话，能加括号就加括号！！

1.2.给一个数n，确定它的二进制表示中的第x位是0还是1（按位与）

要确定一个数 n 的二进制表示中的第 x 位是 0 还是 1，可以使用位运算。在计算机科学中，我们通常从右到左进行位编号，即最低有效位（Least Significant Bit, LSB）为第 0 位，然后依次向左递增。

假设 x 是从右向左的第 x 位（从 0 开始编号），你可以通过以下步骤来确定这一位是 0 还是 1：

右移操作：将 n 右移 x 位，使得目标位成为最低有效位。
按位与操作：将右移后的数与 1 进行按位与操作，以提取最低有效位。

具体步骤如下：

将 n 右移 x 位：n≫x
将结果与 1 进行按位与操作：(n≫x)&1

如果结果是 0，则第 x 位是 0；如果结果是 1，则第 x 位是 1。

假设我们有一个数 n = 29，并且我们想知道它的二进制表示中的第 x = 3 位（从右向左，从0开始编号）是0还是1。

首先，我们需要知道29的二进制表示。29的二进制是 11101。
现在，我们想要确定的是从右数第4位（因为x是从0开始的，所以x=3对应的是第4位），也就是最左边的1（如果我们从右向左数的话，它是第5位，但从0开始数就是第4位）。
但是，为了使用位运算，我们不需要手动转换到二进制。我们可以直接对数字进行位运算来确定这一位。

步骤如下：

将 n 右移 x 位。这会将我们感兴趣的位移动到最低有效位（LSB）。

 n >> x = 29 >> 3 = 3 （因为29的二进制是11101，右移3位后变成00011，即十进制的3）

然后，我们将结果与1进行按位与操作，以提取最低有效位。

因为3的二进制是00011，1的二进制是00001，那么00011&00001就只能得到0或者1，而且这个值一定是右边第一位决定的！！！

其他位置与0&一定得到0，所以结果是0还是1取决于n>>x的右边第一位是0还是1.

(n >> x) & 1 = 3 & 1 = 1

因为结果是1，所以我们可以确定29的二进制表示中的第3位（从0开始数）是1。

1.3.将一个数n的二进制表示的第x位修改成1（按位或）

题目要求将一个数 n 的二进制表示中的第 x 位（从0开始计数）修改成1。这意味着无论该位原本是什么值（0或1），我们都希望将其设置为1。

为了完成这个任务，我们需要遵循以下步骤：

理解二进制表示：每个整数都可以表示为二进制数，其中每一位要么是0要么是1。
定位目标位：我们需要找到第 x 位，这里 x 是从右向左数的，最低位（Least Significant Bit, LSB）是第0位。
创建掩码：为了只影响第 x 位，我们需要创建一个掩码。这个掩码在第 x 位上是1，其他位上都是0。这可以通过将1左移 x 位来实现。
应用掩码：使用按位或（OR）运算将原数 n 与掩码进行运算。按位或运算的特点是，只要两个操作数中对应位有一个是1，结果位就是1。因此，这会确保 n 的第 x 位被设置为1，而不改变其他位。

举例：

假设我们有一个数 n = 13，其二进制表示为 1101。我们希望将第2位（从0开始计数）修改为1。

原数：n = 13，二进制为 1101。
定位目标位：第2位（从右向左数，从0开始）。
创建掩码：将1左移2位得到 1 << 2 = 4，二进制为 0100。
应用掩码：将原数 1101 与掩码 0100 进行按位或运算：
- 第0位：1 OR 0 = 1
- 第1位：1 OR 0 = 1
- 第2位：0 OR 1 = 1（这里我们确保了第2位被设置为1）
- 第3位：1 OR 0 = 1
结果是 1111，即十进制的15。

因此，将数 13 的二进制表示中的第2位修改为1后，我们得到了数 15。

1.4.将一个数n的二进制表示的第x位修改成0

将一个数 n 的二进制表示中的第 x 位（从0开始计数）修改成0，我们可以按照以下步骤进行：

理解二进制表示：每个整数在内存中都有一个二进制表示，每一位要么是0要么是1。
定位目标位：找到要修改的第 x 位，这里 x 是从右向左数的，最低位是第0位。
创建清零掩码：为了只影响第 x 位，我们需要创建一个掩码，这个掩码在第 x 位上是0，其他位上都是1。这可以通过以下步骤实现：
- 首先，使用 1 << x 创建一个在第 x 位上是1，其他位上是0的掩码。
- 然后，对这个掩码进行按位取反（~），得到一个新的掩码，这个掩码在第 x 位上是0，其他位上都是1。这个掩码就是我们需要的清零掩码。
应用清零掩码：使用按位与运算符（&）将原数 n 与清零掩码进行运算。这将确保 n 的第 x 位被设置为0，而不改变其他位。

举例：

假设我们有一个数 n = 13，其二进制表示为 1101。我们希望将第1位（从0开始计数）修改为0。

原数：n = 13，二进制为 1101。
定位目标位：第1位。
创建清零掩码：
- 首先，使用 1 << 1 创建一个掩码，二进制表示为 0010。
- 然后，对这个掩码进行按位取反，得到清零掩码 ~0010 = 11011111111111111111111111111101（对于32位整数，省略了前导零）。但在这个例子中，我们只需要考虑与 n 相同位宽的部分，即 1101 对应的二进制位数。不过，由于我们使用的是32位（或更多位）的整数，实际的掩码会包含更多的1。但在按位与运算中，超出 n 位宽的部分不会影响结果。
- 简化后，我们可以认为清零掩码在 n 的位宽内是 1101（但第1位实际上是我们要清零的位，所以这里只是为了说明掩码的其他位是1）。然而，重要的是要理解我们实际上使用的是 ~(1 << 1) 得到的掩码，它确保了除了第1位之外的所有位都是1。
应用清零掩码：将原数 1101（即13）与清零掩码进行按位与运算。由于清零掩码在第1位上是0，其他位上是1，因此运算结果将是 1101 & 1101111...1101（省略号表示中间可能有很多1），但在 n 的位宽内，这等同于 1101 & 1101 = 1100。

正确的运算应该是：13 & ~(1 << 1) = 1101 & 11011111111111111111111111111101（在32位环境中），但由于我们只关心与 n 相同位宽的部分，所以也就是1101&1101，所以结果是 1100，即十进制的12。

1.5.提取一个数n二进制表示中最右侧的1

C++原码，反码，补码，位运算符(＜＜，＞＞，|，^，&）_c++补码-CSDN博客

提取一个数 n 二进制表示中最右侧的1（也称为最低有效位或最低设置位），我们可以使用位运算中的按位与（AND）运算符和一个特定的掩码来实现。不过，在这个特定情况下，有一个更简单且常用的方法，即使用 n & -n。

解释

负数表示：在计算机中，负数通常使用二进制补码表示。对于一个正整数 n，其二进制补码表示就是它的原码。但是，对于负数 -n，其补码表示是 n 的二进制表示取反后加1。
取反与加1：当我们对 n 取反时，所有的0变成1，所有的1变成0。然后，当我们对这个取反后的数加1时，会从最低位（最右侧）开始，遇到第一个0时停止进位，并将这个0及其之后的所有位都设置为1，而之前的所有位都保持不变（但由于是取反后的数，所以它们实际上是原数中对应位置的相反值）。
与运算：现在，我们有了 n 和 -n 的二进制表示。由于 -n 的最低位（在补码表示中）是1（因为它是通过 n 取反加1得到的），并且这个1是 -n 中从右往左数的第一个1，因此 n & -n 的结果将只在这个位置上为1，其他位置都为0。这正是我们想要的——n 中最低位的1。

例子

假设 n = 10，其二进制表示为 1010。

取 n 的相反数 -n = -10，我们知道10的二进制表示方式是1010，我们对它进行按位取反得到0101，然后再加1得到0110，所以我们很容易就得到-10的二进制补码表示为 0110（这里省略了高位的1，因为它们不会影响结果）。
n & -n 实际上就是 1010 & 0110（这里省略了高位的1，因为它们不会影响结果）。
按位与运算的结果是 0010，这是 n 中最低位的1所对应的值（在这个例子中，它实际上是2）。

但是，重要的是要理解，我们并不关心 0010 这个具体的二进制值，而是关心它表示的位置——即它是 n 中最低位的1。如果我们只关心这个位是否被设置，而不关心它的具体值，那么我们可以说 n & -n 的结果是一个掩码，这个掩码只在 n 中最低位的1的位置上为1。

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

利用 n & (n - 1)：

一个简单且常用的方法是使用 n & (n - 1)。
当我们从 n 中减去1时，二进制表示中最右侧的1会变成0，而这个1之后的所有0都会变成1（这是一个二进制数的特性，称为“借位”或“进位的逆过程”）。
然后，我们将这个结果与原始的 n 进行按位与运算。由于 n 中最右侧的1之后的位都是0，而 n - 1 在这些位上都是1（除了最右侧的那个由1变0的位），所以按位与运算的结果会将这些位都设置为0。
同时，由于 n 和 n - 1 在最右侧的1之前的位都是相同的，所以按位与运算不会改变这些位的值。

例子

假设 n = 10，其二进制表示为 1010。

计算 n - 1，得到 9，其二进制表示为 1001。
计算 n & (n - 1)，即 1010 & 1001。
按位与运算的结果是 1000，这是 n 中去掉最右侧的1之后的结果（在这个例子中，它实际上是8）。

因此，使用 n & (n - 1) 可以快速且有效地将一个数 n 二进制表示中最右侧的1设置为0。

1.7.异或（^）运算的运算律

大家记住下面这3条规律即可

a ^ b ^ c == b ^ a ^ c == b ^ c ^ a ==……

a ^ a == 0

a ^ 0 == a

2.小练习

题目一——191. 位1的个数 - 力扣（LeetCode）

思路及解法

我们可以直接循环检查给定整数 n 的二进制位的每一位是否为 1。

具体代码中，当检查第 i 位时，我们可以让 n 与 $2^i$ 进行与运算，当且仅当 n 的第 i 位为 1 时，运算结果不为 0。

class Solution {
public:
    int hammingWeight(int n) {
        int ret = 0;
        for (int i = 0; i <= 31; i++) {//注意这里为什么选择i的最大限制是31呢？看题目条件就知道了
            if (n & (1 << i)) {
                ret++;
            }
        }
        return ret;
    }
};

题目二——338. 比特位计数 - 力扣（LeetCode）

如果我们按照上面那题的思路，那我们很快就能写出下面这个代码

class Solution {
public:
    std::vector<int> countBits(int n) {
        // 初始化一个大小为n+1的整数向量，所有元素初始化为0
        // 之所以大小为n+1，是因为要包含从0到n的所有整数
        std::vector<int> res(n + 1);
        
        // 遍历从0到n的每个整数
        for(int j = 0; j <= n; j++) {
            int sum = 0; // 用于累加整数j的二进制形式中1的个数
            
            // 遍历整数的每一位（这里假设最大检查到17位，但通常应根据n的大小动态决定）
            for(int i = 0; i < 17; i++) {
                // 检查整数j的第i位是否为1
                // (j & (1 << i)) 通过位与操作和左移操作来实现
                if(j & (1 << i)) {
                    sum++; // 如果第i位是1，则累加器sum加1
                }
            }
            
            // 将计算得到的1的个数存储在结果向量的相应位置
            res[j] = sum;
        }
        
        // 返回存储了每个整数二进制中1的个数的向量
        return res;
    }
};

题目三——461. 汉明距离 - 力扣（LeetCode）

看完这题，我们很容易想到让x^y得到一个结果res，然后循环判断这个元素有多少个有效的1

按位异或^（相同为0，相异为1）

class Solution {
public:
    int hammingDistance(int x, int y) {
        int res=x^y,sum=0;
        for(int n=0;n<=31;n++)
        {
            if(res&(1<<n))
            {
                sum++;
            }
        }
        return sum;
    }
};

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

这道题使用异或是最简单的了

因为异或有下面几个性质

a ^ b ^ c == b ^ a ^ c == b ^ c ^ a ==……

a ^ a == 0

a ^ 0 == a

这就意味着我们可以一直让相邻数组元素异或下去，最后得到的就是我们只有一个的元素。

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

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

我们直接看怎么做即可！

全体异或：
- 我们首先遍历数组中的每个元素，将它们全部进行异或运算，得到一个结果xorsum。
- 由于异或运算满足交换律和结合律，且任何数和自身异或的结果为0，任何数和0异或的结果为它本身，因此xorsum最终将是两个不重复元素的异或结果。
找出最低位的1：
- 首先，我们得知道我们为什么要找最低位的1？
- 因为xorsum最终将是两个不重复元素的异或结果，而异或是相同为0，相异为1。最低位的1位置就刚好是它们a，b的不同之处。我们下面就会根据这个不同之处算出这两个只出现一次的数a，b。
- 接下来，我们需要确定xorsum中最低位的1的位置。这可以通过xorsum & (-xorsum)来实现。
- 在二进制表示中，一个数的负数是通过对该数的每一位取反（即0变1，1变0）并加1得到的。因此，xorsum & (-xorsum)的结果将是xorsum中最低位的1所对应的值（即最低位的1及其后面的0组成的数）。
- 需要特别注意的是，当xorsum等于INT_MIN（即-2^31）时，由于INT_MIN的绝对值超出了int类型的表示范围，我们不能直接对INT_MIN取负号来计算-INT_MIN（这样会导致溢出）。在这种情况下，xorsum的所有位（除了符号位）都是1，因此最低位的1实际上就是整个xorsum的值，即INT_MIN。
分组异或：
- 现在我们已经知道了xorsum中最低位的1的位置，我们可以根据数组中每个元素的该位是否为1来将它们分成两组。
- 由于每个重复元素都会出现在同一组中，而两个不重复元素会分别出现在两组中，因此我们可以分别对两组元素进行异或运算来得到这两个不重复元素。
- 具体来说，我们遍历数组中的每个元素，如果元素的该位为1，则将其异或到type1上；如果元素的该位为0，则将其异或到type2上。最终，type1和type2将分别是两个不重复元素的值。

class Solution {
public:
    std::vector<int> singleNumber(std::vector<int>& nums) {
        // 初始化一个变量xorsum，用于存储所有数字的异或结果
        int xorsum = 0;
        
        // 遍历nums中的每个数字，进行异或运算
        for (int num : nums) {
            xorsum ^= num; // xorsum等于xorsum和num的异或结果
        }
        
        // 找出xorsum中最低位的1所对应的值
        // 注意处理INT_MIN的特殊情况，因为INT_MIN的绝对值超出了int类型的表示范围
        // 所以当xorsum等于INT_MIN时，我们直接取xorsum作为lsb
        // 否则，我们通过xorsum & (-xorsum)来计算lsb
        int lsb;
        if (xorsum == INT_MIN) {
            lsb = INT_MIN;
        } else {
            lsb = xorsum & (-xorsum); // lsb是xorsum中最低位的1的值
        }
        
        // 初始化两个变量type1和type2，用于分别存储两组数字的异或结果
        int type1 = 0, type2 = 0;
        
        // 再次遍历nums中的每个数字，根据数字的最低位是否为1分组进行异或运算
        for (int num : nums) {
            // 如果num的最低位与lsb的最低位相同（即都为1），则将num异或到type1上
            if (num & lsb) {
                type1 ^= num;
            }
            // 否则，将num异或到type2上
            else {
                type2 ^= num;
            }
        }
        
        // 返回一个包含type1和type2的向量，即只出现一次的两个数字
        return {type1, type2};
    }
};

3.大练习

3.1.题目六——面试题 01.01. 判定字符是否唯一 - 力扣（LeetCode）

这个题目想必我就不必多说了吧！！！题目很简单！

但是像这种面试题一遍不会很难，但是会有多种解法

3.1.1.哈希表解法（unordered_map模拟）

就判断唯一性而言，怎么能忘了哈希表呢？必须先上代码

class Solution {
public:
    bool isUnique(string astr) {
        bool res = true; // 初始化结果变量res为true，假设字符串中的字符都是唯一的
        unordered_map<char, int> hash; // 定义一个unordered_map（哈希表），用于存储字符及其出现的次数

        // 遍历字符串astr中的每个字符
        for (int a = 0; a < astr.length(); a++) {
            // 对于每个字符，将其在哈希表中的计数加一
            hash[astr[a]]++;
        }

        // 再次遍历字符串astr中的每个字符
        for (int n = 0; n < astr.length(); n++) {
            // 检查当前字符在哈希表中的计数是否大于1
            // 如果大于1，说明该字符在字符串中重复出现，将结果变量res设置为false
            if (hash[astr[n]] > 1) {
                res = false;
            }
        }

        // 返回结果变量res的值，表示字符串中的字符是否都是唯一的
        return res;
    }
};

虽然1时间复杂度是O(N)，但是这个解法的空间复杂度不太行，因为还是创建了哈希表

3.1.2.位图解法

我们仔细看下面这个

只有小写字母，那意味着只有26个字母。所以我们可以使用位图思想来解题。我们发现一个单独的int就有32位比特位，每个比特位都能存储信息。于是我们可以像下面这样，一个比特位代表一个字母，这样子我们只要26个比特位就能表示出所有的小写字母，我们让0代表该字母没出现过，1代表该字符出现过。

不过，我们还能进行优化！！！

我们可以使用鸽巢原理（抽屉原理）

因为我们有26个英文字母，当字符串长度大于26的话，那就说明一定有重复字符的。那么我们直接返回false即可。

class Solution {
public:
    bool isUnique(string astr) {
        // 如果字符串长度大于26，由于只有26个小写字母，因此必然存在重复字符
        if (astr.length() > 26) {
            return false;
        }
        
        bool res = true; // 初始化结果变量res为true，假设字符串中的字符都是唯一的
        
        int bitmap = 0; // 定义一个整数变量bitmap作为位图，用于记录字符是否出现过
                        // 初始化为0，表示所有字符都未出现过

        // 遍历字符串astr中的每个字符
        for (int i = 0; i < astr.length(); i++) {
            // 检查当前字符（转换为小写字母后）是否已经出现过
            // 通过位运算检查bitmap的对应位是否为1
            // (astr[i] - 'a') 计算得到当前字符相对于'a'的偏移量（0到25）
            // 1 << (astr[i] - 'a') 将1左移上述偏移量位，得到一个只在对应位上为1的数
            // bitmap & (1 << (astr[i] - 'a')) 检查bitmap的对应位是否为1
            if (bitmap & (1 << (astr[i] - 'a'))) {
                // 如果对应位为1，说明当前字符已经出现过，将结果变量res设置为false
                res = false;
            } else {
                // 如果对应位为0，说明当前字符未出现过，将其标记为已出现
                // 通过位运算将bitmap的对应位设置为1
                bitmap = bitmap | (1 << (astr[i] - 'a'));
            }
        }

        // 返回结果变量res的值，表示字符串中的字符是否都是唯一的
        return res;
    }
};

3.2.题目七——268. 丢失的数字 - 力扣（LeetCode）

3.2.1.哈希表解法（unordered_map模拟）

这题和上题差不了太多，还是可以使用哈希表。

class Solution {
public:
    int missingNumber(std::vector<int>& nums) {
        int res;  // 用于存储缺失的数字
        std::unordered_map<int, int> hash;  // 使用unordered_map来记录每个数字出现的次数
        
        // 遍历nums数组，将每个数字作为键，其出现次数作为值存入hash中
        for (int n = 0; n < nums.size(); n++) {
            hash[nums[n]]++;
        }
        
        // 遍历从0到nums.size()的数字
        // 因为数组是从0开始的，且长度为n，所以理论上应该包含0到n的数字，其中一个缺失
        for (int n = 0; n <= nums.size(); n++) {
            // 如果hash中不存在当前遍历到的数字n，则n就是缺失的数字
            if (hash.count(n) == 0) {
                res = n;
            }
        }
        
        // 返回找到的缺失数字
        return res;
    }
};

3.2.2.高斯求和公式

高斯求和公式，也被称为等差数列求和公式，是用来计算等差数列前n项和的公式。等差数列是一种特殊的数列，其中任意两个相邻项的差都是常数。这个常数被称为公差。

高斯求和公式的一般形式为：

通过这个式子，我们也可以很快做出这道题目

class Solution {
public:
    int missingNumber(std::vector<int>& nums) {
        // 使用高斯求和公式计算从0到nums.size()的整数序列之和
        // 高斯求和公式：(首项 + 末项) * 项数 / 2
        // 在这里，首项是0，末项是nums.size()，项数是nums.size() + 1（因为包括0）
        int sum1 = (0 + nums.size()) * (nums.size() + 1) / 2;
 
        // 初始化一个变量sum2来存储数组nums中所有元素的和
        int sum2 = 0;
        
        // 遍历数组nums，计算所有元素的和
        for (int n = 0; n < nums.size(); n++) {
            sum2 += nums[n];
        }
 
        // 返回理论上完整序列的和减去数组中实际存在的数字之和，即得到缺失的数字
        return sum1 - sum2;
    }
};

3.2.3. 异或解法

我们知道异或有下面三个性质

a ^ b ^ c == b ^ a ^ c == b ^ c ^ a ==……

a ^ a == 0

a ^ 0 == a

那么我们只需执行两次for循环

第一次for循环让所有数组元素异或得到一个sum
第二次for循环让[0,n]所有数字都和sum异或，这样子出现两次的数就会被消除掉，只出现了一次的数就会保留下来，最后得到的这个数就是我们找的结果

class Solution {
public:
    int missingNumber(std::vector<int>& nums) {
        int res = 0;  // 初始化结果变量res为0，用于存储异或运算的中间结果和最终结果
        
        // 遍历nums数组，对每个元素执行异或操作，并将结果累加到res中
        // 由于异或运算的性质，相同的数字异或后会抵消为0，不同的数字异或后会保留差异
        for (int i = 0; i < nums.size(); i++) {
            res ^= nums[i];
        }
        
        // 遍历从0到nums.size()的数字，对每个数字执行异或操作，并将结果累加到res中
        // 这一步的目的是将原本应该在数组中的数字（包括缺失的那个）都异或一遍
        // 由于前面已经将数组中的数字异或过了，所以这一步相当于只异或了缺失的那个数字（和nums.size()，但nums.size()会与自身的异或结果抵消）
        for (int i = 0; i <= nums.size(); i++) {
            res ^= i;
        }
        
        // 此时，res中存储的就是缺失的数字，因为异或运算具有可逆性和交换律
        // 所有原本应该在数组中的数字都被异或了两遍（抵消为0），只剩下缺失的那个数字只被异或了一次
        return res;
    }
};

3.3.题目八—— 371. 两整数之和 - 力扣（LeetCode）

3.3.1.面试解法

说实话，在面试的时候，我们完全就可以像下面这样子做

class Solution {
public:
    int getSum(int a, int b) {
        return a+b;
    }
};

3.3.2.异或用于加法运算

首先，我们来看异或运算的基本性质：

对于任意两个二进制数a和b，a XOR b的结果是在对应位上，如果a和b的该位不同则为1，相同则为0。

这个性质使得异或运算在不考虑进位的情况下，与无进位加法相似。

我们举一个例子

我们发现这个没有进位啊？

但是进位只能是1和1相遇才能进位，其他组合是不能进位的，所以所有的进位情况就如下图

我们发现这样子一个运算就是按位与操作。于是我们又能接着写

但是我们发现，我们这个进位是进到前一位的！！！所以我们要将进位往左边移动1个位置

接下来我们就要重复上面两步求得结果！！重复，重复，那什么时候终止呢？

我们发现当进位为0的时候，就没有继续重复下去的必要了，这个时候我们选择停止，然后返回a^b即可。我们很快就写出下面这个代码

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

3.4.题目九——137. 只出现一次的数字 II - 力扣（LeetCode）

这个题目很简单啊

3.4.1.哈希表（unordered_map模拟）

这个很简单，我不过多赘述，就直接写代码就好了

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int,int> hash;
        for(int i=0;i<nums.size();i++)
        {
            hash[nums[i]]++;
        }
        int res;
        for(int n=0;n<nums.size();n++)
        {
            if(hash[nums[n]]==1)
            {
                res=nums[n];
            }
        }
        return res;
    }
};

3.4.2.位运算解法

这道题的特点就是有一个数出现了1次，其余所有的数都出现了3次。

由于数组中的元素都在 int（即 32 位整数）范围内，因此我们可以依次计算每个元素的每一个二进制位是 0 还是 1。

对于数组中的每一个元素 x，我们使用位运算 (x >> i) & 1 得到 x 的第 i 个二进制位，并将它们按相同比特位进行相加，其中每个比特位最后相加的结果一定是下面这4种情况里的一种

3n个0 + 0
3n个0 + 1
3n个1 + 0
3n个1 + 1

我们发现，怎么都有3啊？我们直接让它们都%3，得到下面

(3n个0 + 0 )%3 ==0
(3n个0 + 1 )%3 ==1
(3n个1 + 0 )%3 ==0
(3n个0 + 1 )%3 ==1

我们发现，这个结果怎么都能和那个出现了1次的数对上啊！！也就是说我们可以通过这个方法来算出这个结果，而不是去找这个结果

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0; // 初始化结果变量，用于存储最终只出现一次的数字
 
        // 遍历整数的32个比特位（假设整数是32位的）
        for (int i = 0; i <= 31; i++) {
            int sum = 0; // 初始化sum为0，用于计算所有数组元素在第i位比特位的总和
 
            // 遍历数组中的每个元素
            for (int n = 0; n < nums.size(); n++) {
                // 检查当前元素nums[n]的第i位是否为1
                if (nums[n] & (1 << i)) {
                    sum++; // 如果是1，则sum加1
                }
            }
 
            // 对sum进行模3运算，得到余数
            sum %= 3;
 
            // 如果sum等于1，说明只出现一次的数字在第i位上是1
            if (sum == 1) {
                // 使用位运算将res的第i位设置为1
                res |= (1 << i);
            }
            
            // 注意：这里不需要else分支，因为sum可能等于0，这种情况不需要修改res，因为本来就是0
        }
 
        // 返回只出现一次的数字
        return res;
    }
};

3.5.题目十——面试题 17.19. 消失的两个数字 - 力扣（LeetCode）

3.5.1.位运算解法

不知道大家有没有发现这道题目和上面的题目五特别像。

这道题的算法思想是丢失的数字+只出现一次的数字|||这两道题的糅合

如果我们把下面这两个当成是一个对象来处理

那么这题不就变成了只有两个数字出现了1次，其余数字都出现了2次吗？

那这个题的思路不就和上面的题目五一样了吗

我们直接看怎么做即可！

全体异或：
- 我们首先遍历数组中的每个元素和那个【1，N+2】的所有整数，将它们全部进行异或运算，得到一个结果sum1。
- 由于异或运算满足交换律和结合律，且任何数和自身异或的结果为0，任何数和0异或的结果为它本身，因此sum1最终将是两个不重复元素的异或结果。
找出最低位的1：
- 首先，我们得知道我们为什么要找最低位的1？
- 因为sum1最终将是两个不重复元素的异或结果，而异或是相同为0，相异为1。最低位的1位置就刚好是它们a，b的不同之处。我们下面就会根据这个不同之处算出这两个只出现一次的数a，b。
- 接下来，我们需要确定sum1中最低位的1的位置。这可以通过xorsum & (-xorsum)来实现。
- 在二进制表示中，一个数的负数是通过对该数的每一位取反（即0变1，1变0）并加1得到的。因此，sum1 & (-sum1)的结果将是sum1中最低位的1所对应的值（即最低位的1及其后面的0组成的数）。
分组异或：
- 现在我们已经知道了sum1中最低位的1的位置，我们可以根据数组中每个元素的该位是否为1来将它们分成两组。
- 由于每个重复元素都会出现在同一组中，而两个不重复元素会分别出现在两组中，因此我们可以分别对两组元素进行异或运算来得到这两个不重复元素。
- 具体来说，我们遍历数组中的每个元素，如果元素的该位为1，则将其异或到res1上；如果元素的该位为0，则将其异或到res2上。最终，res1和res2将分别是两个不重复元素的值。

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        // 初始化sum1为0，用于存储数组中所有元素的异或结果
        int sum1 = 0;
        // 遍历数组nums，计算所有元素的异或和
        for (int n = 0; n < nums.size(); n++) {
            sum1 ^= nums[n];
        }
        // 将从1到nums.size()+2（因为有两个数字缺失）的所有整数与sum1进行异或
        // 此时sum1变为两个缺失数字的异或结果
        for (int i = 1; i <= nums.size() + 2; i++) {
            sum1 ^= i;
        }

        // 找出两个缺失数字的异或结果中的最低设置位（即二进制表示中最低位的1）
        // 这可以通过sum1与-sum1的按位与操作得到
        int sum2 = sum1 & (-sum1);
        
        // 初始化res1和res2为0，用于存储最终找到的两个缺失数字
        int res1 = 0, res2 = 0;
        
        // 遍历数组nums，根据最低设置位将数字分成两组进行异或
        // 如果nums[i]的最低设置位与sum2的最低设置位相同，则将其加入第一组（res1）
        // 否则，将其加入第二组（res2）
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] & sum2) {
                res1 ^= nums[i];
            } else {
                res2 ^= nums[i];
            }
        }
        
        // 同样地，将从1到nums.size()+2的数字也根据最低设置位分成两组进行异或
        // 这一步是为了从完整的数字集合中恢复出两个缺失的数字
        for (int i = 1; i <= nums.size() + 2; i++) {
            if (i & sum2) {
                res1 ^= i;
            } else {
                res2 ^= i;
            }
        }
        
        // 返回找到的两个缺失数字
        return { res1, res2 };
    }
};