【优选算法篇】探索位运算的宇宙：简单规则背后的复杂逻辑（中篇）

须知

💬 欢迎讨论：如果你在学习过程中有任何问题或想法，欢迎在评论区留言，我们一起交流学习。你的支持是我继续创作的动力！ 👍 点赞、收藏与分享：觉得这篇文章对你有帮助吗？别忘了点赞、收藏并分享给更多的小伙伴哦！你们的支持是我不断进步的动力！ 🚀 分享给更多人：如果你觉得这篇文章对你有帮助，欢迎分享给更多对C++算法感兴趣的朋友，让我们一起进步！

接上篇：【优选算法篇】位运算小课堂：从入门到精通的奇妙之旅（上篇）-CSDN博客

引言：通过上篇文章带大家简单了解“位运算算法”，小试牛刀。接下来将让大家感受一下位运算在解题的妙处。

1. 高效与基础
   • 位运算直接操作二进制位，具有高效、低级别、常数时间复杂度的特性，是算法优化的重要工具。
2. 考察重点
   • 面试中常考查位运算基础知识、位运算性质 和 实际应用场景，例如：
     • 异或：去重、找唯一元素。
     • 与/或：掩码操作、特定位判断。
     • 移位：快速乘除以2的幂。
3. 典型题型
   • 找出唯一数：数组中一个数出现一次，其他数出现两次/三次。
   • 判断奇偶：通过 num & 1。
   • 位掩码：权限管理、分组操作。
   • 优化求和：连续数组求和、K次出现问题。
4. 面试中的价值
   • 考察代码功底：理解位运算需要扎实的基础。
   • 解决实际问题：在性能敏感场景中，位运算常用于算法优化。
   • 考察思维能力：巧妙运用位运算解决复杂问题，体现编程思维的灵活性。

总结：掌握位运算不仅可以帮助快速通过面试常见题型，更能展示对计算机底层机制的理解和高效解决问题的能力。

前言

位运算是计算机程序设计中的基础且高效的运算方式，直接对二进制位进行操作，适合解决性能敏感场景下的复杂问题。

• 底层原理：计算机内部数据存储是二进制的，因此位运算直接作用于二进制位，执行速度极快。
• 应用广泛：在算法优化、数据压缩、权限管理、位图处理等场景中，位运算具有不可替代的优势。

"位运算算法：从基础到高级场景的全面解析"

1. C++ 位运算算法 进阶详解

1.1 位运算概念

位运算是对整数的二进制表示进行按位操作的运算，包括：

基本运算

1. 按位与（&）
   • 规则：两个二进制位都为 1，结果为 1，否则为 0。
   • 应用：用于清零、掩码操作、判断奇偶。
     • 示例：5 & 3 = 0101 & 0011 = 0001 (1)
2. 按位或（|）
   • 规则：两个二进制位中只要有一个为 1，结果为 1。
   • 应用：用于设置特定位为1。
     • 示例：5 | 3 = 0101 | 0011 = 0111 (7)
3. 按位异或（^）
   • 规则：两个二进制位相同为 0，不同为 1。
   • 应用：用于找不同、交换变量、去重。
     • 示例：5 ^ 3 = 0101 ^ 0011 = 0110 (6)
4. 按位取反（~）
   • 规则：将二进制位的 0 变 1，1 变 0。
   • 应用：求补码、快速清零。
     • 示例：~5 = ~0101 = 1010（假设4位）
5. 左移（<<）
   • 规则：将二进制位向左移动指定位置，右边补 0。
   • 应用：快速计算 x * 2^n。
     • 示例：5 << 1 = 0101 << 1 = 1010 (10)
6. 右移（>>）
   • 规则：将二进制位向右移动指定位置。
     • 算术右移：高位用符号位填充（保持正负性）。
     • 逻辑右移：高位补0。
   • 应用：快速计算 x / 2^n。
     • 示例：5 >> 1 = 0101 >> 1 = 0010 (2)

1.2 经典应用

1.2.1 判断奇偶数

方法：通过按位与操作 n & 1。

• 原理：
  • 奇数的二进制最低位是 1。
  • 偶数的二进制最低位是 0。

bool isOdd(int n) { return n & 1; // 返回 true 表示奇数 }

1.2.2 交换两个数（不使用额外变量）

方法：使用异或运算 ^。

• 原理：异或满足交换律和结合律。

void swap(int &a, int &b) { a ^= b; b ^= a; a ^= b; }

1.2.3 判断二进制中某一位是否为1

方法：使用按位与操作 n & (1 << i)，其中 i 是目标位的位置

bool isBitSet(int n, int i) { return n & (1 << i); }

1.2.4 清零最低位的1

方法：n & (n - 1)

• 原理：n - 1 将最低位的 1 变为 0，并将该位之后的所有位取反。

int countOnes(int n) { int count = 0; while (n != 0) { n &= (n - 1); // 清零最低位的1 count++; } return count; }

1.2.5 计算一个数的2的幂次方倍

方法：通过左移操作 n << k。

• n << k 等价于 n * 2^k

int powerOfTwo(int n, int k) { return n << k; // n 乘以 2^k }

1.2.6 位掩码应用（权限管理）

应用：将某个位设为1、清零、反转。

• 设置某一位为1：n | (1 << i)
• 清零某一位：n & ~(1 << i)
• 反转某一位：n ^ (1 << i)

int setBit(int n, int i) { return n | (1 << i); } // 设置第i位为1 int clearBit(int n, int i) { return n & ~(1 << i); } // 清除第i位 int toggleBit(int n, int i) { return n ^ (1 << i); } // 反转第i位

1.3 总结

1. 位运算特点
   • 高效：直接操作二进制位，执行速度极快。
   • 简洁：常用于问题的简化和优化。
2. 经典应用场景
   • 奇偶判断
   • 清除最低位的1
   • 找出唯一出现的元素
   • 位掩码（权限管理）
   • 数据压缩、加密等领域
3. 面试考察重点
   • 基本位运算的理解与掌握
   • 异或运算的巧妙应用
   • 高效解决数组、数字处理相关问题

位运算 是计算机底层运算的基石，掌握它能够高效解决许多算法和面试题目。

2. 题目1：面试题01.01. 判定字符是否唯一

题目链接：面试题 01.01. 判定字符是否唯一 - 力扣（LeetCode）

题目描述：

2.1 算法思路：

1. 问题简化
   • 字符串只包含小写字母（26个），可以用一个整数 int ret 的 26 位来表示每个字符是否出现过。
   • 每一位对应一个字母：
     • 第 i 位为 1：表示字符 'a' + i 已经出现过。
     • 第 i 位为 0：表示字符 'a' + i 尚未出现。
2. 位运算
   • 按位与（&）：判断某一位是否为1。
   • 按位或（|）：将某一位设置为1。
3. 字符检查流程
   • 遍历字符串中的每个字符。
   • 计算该字符在二进制表示中的位置 i = s - 'a'。
   • 使用 (ret >> i) & 1 判断该位是否为 1：
     • 如果是，说明字符重复，返回 false。
     • 如果不是，使用 ret |= (1 << i) 将该位设置为 1。
   • 遍历完成后，返回 true。
4. 优化：
   • 若字符串长度超过 26，必然有重复字符，可以直接返回 false。

2.2 示例代码：

class Solution 
{
public:
    bool isUnique(string astr) 
    {
        // 如果字符串长度大于26，字符必然重复
        if (astr.size() > 26)  
            return false;

        int ret = 0; // 用于存储字符出现情况的位掩码

        for (auto s : astr) 
        {
            int i = s - 'a'; // 计算当前字符对应的位置（0~25）
            
            // 检查第 i 位是否已经为 1（字符是否已出现）
            if ((ret >> i) & 1) 
                return false;

            // 将第 i 位设置为 1，标记字符已出现
            ret |= (1 << i);
        }
        return true; // 所有字符唯一
    }
};

2.2.1 执行过程示例

输入："abc"

• 初始 ret = 0（所有位为0）。

| 字符 | 位置 i | 检查 (ret >> i) & 1 | 设置 ret |= (1 << i) | ret (二进制) | |------|---------|------------------------|-----------------------|----------------| | 'a'| 0 | 0 | 00000000000000000001 | 00000001 | | 'b'| 1 | 0 | 00000000000000000010 | 00000011 | | 'c'| 2 | 0 | 00000000000000000100 | 00000111 |

结果：所有字符唯一，返回 true。输入："abca"

• 当处理第二个 'a' 时：
  • (ret >> 0) & 1 = 1，说明字符 'a' 已经出现过，返回 false。

2.3 多种解法

2.3.1 解法二：使用哈希集合 (unordered_set)

思路

1. 遍历字符串，将每个字符加入哈希集合。
2. 如果某个字符已经存在于集合中，说明字符重复，返回 false。
3. 遍历结束后，没有发现重复字符，返回 true。

代码实现

class Solution {
public:
    bool isUnique(string astr) {
        unordered_set<char> charSet; // 哈希集合用于存储字符
        for (char ch : astr) {
            if (charSet.count(ch)) { // 字符已存在
                return false;
            }
            charSet.insert(ch); // 插入字符
        }
        return true; // 所有字符唯一
    }
};

时间复杂度：O(n)，其中 n 为字符串长度。

空间复杂度：O(n)，最坏情况下存储所有字符。

2.3.2 解法三：暴力双重循环

思路

1. 使用两层循环，枚举字符串中每一对字符。
2. 如果发现两个字符相等，返回 false。
3. 遍历完成后，没有重复字符，返回 true。

代码实现

class Solution {
public:
    bool isUnique(string astr) {
        int n = astr.size();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (astr[i] == astr[j]) { // 字符重复
                    return false;
                }
            }
        }
        return true; // 所有字符唯一
    }
};

时间复杂度：O(n^2)，其中 n 为字符串长度。

空间复杂度：O(1)，无额外空间使用。

2.3.3 解法四：排序后检查相邻字符

思路

1. 将字符串排序。
2. 排序后，相同的字符会相邻。遍历字符串，如果相邻字符相等，返回 false。
3. 遍历结束后，返回 true。

代码实现

#include <algorithm>
class Solution {
public:
    bool isUnique(string astr) {
        sort(astr.begin(), astr.end()); // 字符串排序
        for (int i = 1; i < astr.size(); i++) {
            if (astr[i] == astr[i - 1]) { // 检查相邻字符是否相等
                return false;
            }
        }
        return true; // 所有字符唯一
    }
};

2.3.4 使用布尔数组标记

思路

1. 使用一个布尔数组（长度256，表示ASCII字符集）标记字符是否出现过。
2. 遍历字符串，如果字符已标记为 true，说明重复。
3. 否则，将字符对应的索引标记为 true。

代码实现

class Solution {
public:
    bool isUnique(string astr) {
        bool charSet[256] = {false}; // ASCII字符集
        for (char ch : astr) {
            if (charSet[ch]) { // 字符已存在
                return false;
            }
            charSet[ch] = true; // 标记字符
        }
        return true; // 所有字符唯一
    }
};

时间复杂度：O(n)，其中 n 为字符串长度。

空间复杂度：O(1)，使用固定大小的数组（256）。

2.3.5 解法总结

2.4 时间复杂度与空间复杂度

1. 时间复杂度：O(n)，其中 n 是字符串的长度。
   • 每个字符需要执行一次位运算，操作为常数时间。
2. 空间复杂度：O(1)，
   • 只使用了一个 int 变量 ret 来存储字符的状态（固定大小）。

2.5 总结

1. 优化特性：
   • 位运算高效处理字符状态，减少了数组或集合的额外空间消耗。
   • 直接使用整数的位操作，适用于字符集较小的情况（如小写字母）。
2. 适用场景：
   • 字符串中字符集已知且较小（如 a-z）。
   • 面试中常考位运算基础与优化。
3. 关键点：
   • 按位与（&） 检查状态。
   • 按位或（|） 设置状态。
   • 位掩码 int 可以高效记录字符出现情况。

3. 题目2：丢失的数字

题目链接：268. 丢失的数字 - 力扣（LeetCode）

题目描述：

3.1 算法思路：位运算（异或法）

1. 异或的性质：
   • a ^ a = 0（相同的数异或为0）。
   • a ^ 0 = a（任何数与0异或，结果为它本身）。
   • 交换律 和 结合律：顺序可以任意调整：a ^ b ^ c = a ^ c ^ b。
2. 问题分析：
   • 数组包含从 0 到 n 的所有数字，除了缺失的一个数字。
   • 如果把 0 ~ n 所有数字的异或结果与数组中的所有数字的异或结果再次异或，它们成对的数字会互相抵消为 0，只剩下缺失的数字。
3. 核心思路：
   • 将数组中的所有元素进行异或。
   • 再将 0 ~ n 范围内的所有数字进行异或。
   • 最终，所有成对的数字会抵消为 0，剩下的即为 缺失的数字。

3.2 代码实现

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int res = 0; // 初始化结果
        int n = nums.size();

        // 异或数组中的所有数字
        for (int i = 0; i < n; i++) {
            res ^= nums[i];
        }

        // 异或 0 ~ n 范围内的所有数字
        for (int i = 0; i <= n; i++) {
            res ^= i;
        }

        return res; // 返回最终结果，即缺失的数字
    }
};

3.2.1 执行过程分析

假设输入：nums = [3, 0, 1] 数组缺失的数字是 2，我们执行以下步骤：

1. 异或数组中的所有数字：

res = 0 res ^= 3 → res = 3 res ^= 0 → res = 3 ^ 0 = 3 res ^= 1 → res = 3 ^ 1 = 2

2. 异或 0 ~ n 范围内的所有数字（n = 3）：

res ^= 0 → res = 2 ^ 0 = 2 res ^= 1 → res = 2 ^ 1 = 3 res ^= 2 → res = 3 ^ 2 = 1 res ^= 3 → res = 1 ^ 3 = 2

最终结果 res = 2，缺失的数字即为 2。

3.3 复杂度分析

3.3.1 时间复杂度

• 两次遍历：
  • 遍历数组一次：O(n)。
  • 遍历 0 ~ n 一次：O(n)。
• 总时间复杂度：O(n)。

3.3.2 空间复杂度

• 使用了一个变量 res 记录异或结果，空间复杂度为 O(1)。

优点总结

1. 时间高效：通过位运算的异或性质，只需线性时间完成。
2. 空间优化：不需要额外的数据结构，只使用常数空间。
3. 适用场景：数字缺失、数组中重复元素等问题，异或法都可以高效解决。

3.4 多种解法

3.4.1 解法二：数学求和法

思路

1. 公式：利用等差数列的求和公式：sum = n * (n + 1) / 2，计算 0 ~ n 的总和。
2. 实际和：计算数组中所有元素的和。
3. 缺失的数字就是 sum - actualSum。

代码实现

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int totalSum = n * (n + 1) / 2; // 0~n 的总和
        int arraySum = 0;
        for (int num : nums) {
            arraySum += num; // 计算数组元素的总和
        }
        return totalSum - arraySum; // 两者之差就是缺失的数字
    }
};

时间复杂度：O(n)

空间复杂度：O(1)

3.4.2 解法三：排序法

思路

1. 对数组进行排序。
2. 遍历排序后的数组，如果索引 i 和数组元素 nums[i] 不相等，说明缺失的数字是 i。
3. 如果所有数字都符合规则，返回 n（最大值）。

代码实现

#include <algorithm>
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end()); // 排序数组
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != i) { // 如果索引与元素不匹配
                return i;
            }
        }
        return nums.size(); // 缺失的是 n
    }
};

3.4.3 解法四：哈希表法

思路

1. 使用哈希表存储数组中的每个元素。
2. 遍历 0~n 范围内的所有数字，判断每个数字是否存在于哈希表中。
3. 如果不存在，返回该数字。

代码实现

#include <unordered_set>
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        unordered_set<int> numSet(nums.begin(), nums.end()); // 将数组存入哈希表
        for (int i = 0; i <= nums.size(); i++) {
            if (numSet.find(i) == numSet.end()) { // 如果数字不在哈希表中
                return i;
            }
        }
        return -1; // 理论上不会执行到这里
    }
};

时间复杂度：O(n)

空间复杂度：O(n)

3.4.4 解法五：数组索引法（标记法）

思路

1. 将数组中的数字标记到一个辅助数组（长度为 n+1）中。
2. 遍历辅助数组，找到没有被标记的位置，即为缺失的数字。

代码实现

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        vector<bool> mark(n + 1, false); // 辅助数组，初始化为false
        for (int num : nums) {
            mark[num] = true; // 标记出现的数字
        }
        for (int i = 0; i <= n; i++) {
            if (!mark[i]) { // 找到未标记的位置
                return i;
            }
        }
        return -1; // 理论上不会执行到这里
    }
};

时间复杂度：O(n)

空间复杂度：O(n)

3.4.5 解法总结

3.5 总结

异或法 是解决 缺失数字 问题的最优解之一，利用位运算性质，简单高效，时间复杂度为 O(n)，空间复杂度为 O(1)。

4. 总结要点

1. 异或运算 是位运算解决重复出现问题的核心思想：
   • 相同为0，0与任何数异或等于数本身。
2. 位统计 + 取模：通过逐位统计 1 的个数，可以解决 K次出现问题。
3. 低位的1：通过提取最低位的1，可以将数字分组，解决两个目标数字的问题。

5. 最后

通过上面几个例题：「判定字符是否唯一」的多种解法、以及「丢失的数字」的位运算方法 我们总结出位运算在数组问题中的高效应用。 位运算 通过将复杂的数字出现次数、分组、去重等问题转化为简单的位级操作（如异或、位统计、取模等），极大地提升了问题求解的效率。 在处理 元素重复出现问题、分组求解问题 以及 高效数值处理 等场景时，位运算展现出显著的性能优势，尤其适用于 大规模数据 和 时间复杂度敏感 的应用场景。

路虽远，行则将至；事虽难，做则必成

亲爱的读者们，下一篇文章再会！！！