自学内容网 自学内容网

【优选算法】--- 位运算

一、常见的位运算总结(重点!)

1、关于位运算的符号

在这里插入图片描述

2、(判断)给一个数字n,确定它的二进制表示中的第X位,是1还是0?

在这里插入图片描述
方法:(n>>x)&1

3、(修改)如何把一个二进制的数字的第x位修改为1?

在这里插入图片描述

方法:n|=(1<<x)

4、(修改)如何将一个数的二进制的第x位修改为0?

在这里插入图片描述
方法:n&= (~(1<<x))

5、(lowbit)提取二进制中最右侧的1

在这里插入图片描述
方法:n&(-n)

6、去除二进制中最右侧的1

在这里插入图片描述
方法:n&(n-1)

7、位运算的优先级?能加() 就加()

8、异或(^)的运算规律

1. a^0=a
2. a^a=0
3. a^b ^ c=a^ (b^c)交换律

二、判定字符是否唯一

1、题目解析

在这里插入图片描述

2、算法原理

在这里插入图片描述

3、代码

class Solution 
{
public:
    bool isUnique(string astr) 
    {
        // 利用鸽巢原理,如果给的字符串数量大于26,必有重复
        if(astr.size()>26) return false;

        int bitmap=0;// 就是刚开始默认32个0
        for(auto ch:astr)
        {
            // 把每个字符转化为他的ASC||码值
            int i=ch-'a';
            // 先判断该位置是否已经存在(1:存在,0:不存在)
            if((bitmap>>i)&1==1) return false;

            // 此时就可以 把第一次出现的进入,位置标为1

            bitmap|=1<<i;
        }
        return true;
    }
};

三、丢失的数字

1、题目解析

在这里插入图片描述

2、算法原理

利用按位异或的规律:
①:a^ 0=a
②:a^ a=0

实际上就是:单身狗问题!

3、代码

class Solution 
{
public:
    int missingNumber(vector<int>& nums) 
    {
        int ret=0;
        // 先把所给的数组 里面的数据异或(^)在一起
        for(auto n:nums) ret^=n;
        
        // 这里的ret保留了之前异或的,再把标准数组异或一下,就相当于所有都异或在一起了
        for(int i=0;i<nums.size()+1;i++) ret^=i; 
        return ret;
    }
};

四、两整数之和

1、题目解析

在这里插入图片描述

2、算法原理

在这里插入图片描述

3、代码

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

            a=x;
            b=y;// 重复上面的步骤
        }
        return a;
    }
};

五、只出现一次的数字||

1、题目解析

在这里插入图片描述

2、算法原理

在这里插入图片描述

3、代码

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++;
            }
            if(sum%3==1)
                ret|=1<<i;// 把第i位修改为1
        }
        return ret;
    }
};

六、消失的两个数字

1、题目解析

在这里插入图片描述

2、算法原理

在这里插入图片描述

3、代码

class Solution 
{
public:
    vector<int> missingTwo(vector<int>& nums) 
    {
        // 假设a,b是消失的数字

        // 1、将所有的数异或到一起
        int tmp=0;
        for(int  x:nums)
        {
            tmp^=x;
        }
        for(int i=1;i<=nums.size()+2;i++)
        {
            tmp^=i;
        }
        // 此时的tmp就是a^b

        // 2、找出a、b比特位不同的那一位
        int diff=0;// 标记比特位不同的几个位置
        for(int i=0;i<32;i++)
        {
            if((tmp>>i)&1==1)
                break;
            else
                diff++;
        }

        // 3、根据diff位的不同,对[1~N]、nums分类异或
        int a=0,b=0;// b存放比特位为1,a存放0
        for(int i=1;i<=nums.size()+2;i++)
        {
            if((i>>diff)&1==1) b^=i;
            else a^=i;
        }
        for(int x:nums)
        {
            if((x>>diff)&1==1) b^=x;
            else a^=x;
        }

        return {a,b};
    }
};

原文地址:https://blog.csdn.net/weixin_75128035/article/details/142760661

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!