算法(5)——位运算

一、位运算概述

• 程序中的所有数在计算机内存中都是以二进制的形式存储的

• 位运算(Bitwise operation)就是直接对整数在内存中的二进制位进行操作，因此其执行效率非常高

• 在程序一般使用位运算进行操作，会大大提高程序的性能

位运算的本质

• 位运算是在二进制之间操作，粗略地说就是 0 和 1 之间的转换

位运算时会将数值转换为32位整型来进行运算，所以位运算遇到小数时，直接处理掉小数部分当成整数来运算，并且要是一个数的二进制表示超过32位，或者运算完后超过32位，那么就会出问题。所以不是所有的情况都适用位运算（可以利用位运算进行取整操作）

二、位运算操作符

位运算操作符有：

• 按位非~

• 按位与&

• 按位或|

• 按位异或^

• 左移<<

• 无符号右移>>>

• 有符号右移>>

想必大家对这些操作符都很熟悉了，我在这里就不过多解释了

三、位运算相关操作

1、给一个数N，确定它的二进制表示中的第X位是0还是1？

（N>>X）&1

2、将一个数N的二进制第X位修改为1

N=N |（1<<X）

3、将一个数N的二进制第X位修改为0

N=N & (~(1<<X)）

4、提取一个数（N）二进制表示中最右侧的1

N & -N

5、干掉一个数（N）二进制表示中最右侧的1

N & (N-1)

注意：我们在位运算时要关注位运算的优先级，我们最好都加括号（），这样就不会出错

四、位运算例题

4.1、判断字符串是否唯一

面试题 01.01. 判定字符是否唯一 – 力扣（LeetCode）

        题目描述：

        算法思路

利⽤「位图」的思想，每⼀个「⽐特位」代表⼀个「字符，⼀个 int 类型的变量的 32 位⾜够表⽰所有的⼩写字⺟。⽐特位⾥⾯如果是 0 ，表⽰这个字符没有出现过。⽐特位⾥⾯的值是 1 ，表⽰该字符出现过。

那么我们就可以⽤⼀个「整数」来充当「哈希表」。        代码实现1

class Solution {
public:
    bool isUnique(string astr) 
    {
        //位图
        int bitmap=0;
        for(auto e:astr)
        {
            int i=e-'a';
            if((bitmap>>i)&1)
            {
                return false;
            }   
            bitmap=bitmap|(1<<i);
        }
        return true;
    }
};

        代码实现2

哈希算法
class Solution {
public:
    bool isUnique(string astr) 
    {
        if(astr.size()>26)
        {
            return false;
        }
        unordered_map<char,int> arr;
        for(int i=0;i<astr.size();i++)
        {
            arr[astr[i]]++;
            if(arr[astr[i]]>1)
            {
                return false;
            }
        }
        return true;
    }
};

4.2、丢失的数字

268. 丢失的数字 – 力扣（LeetCode）

        题目描述

        算法思路

设数组的⼤⼩为 n ，那么缺失之前的数就是 [0, n] ，数组中是在 [0, n] 中缺失⼀个数形成 的序列。

如果我们把数组中的所有数，以及 [0, n] 中的所有数全部「异或」在⼀起，那么根据「异或」 运算的「消消乐」规律，最终的异或结果应该就是缺失的数~

        代码实现

class Solution {
public:
    int missingNumber(vector<int>& nums) 
    {
        int xorsum=0;
        for(auto e:nums)
        {
            xorsum^=e;
        }
        for(int i=1;i<=nums.size();i++)
        {
            xorsum^=i;
        }
        return xorsum;
    }
};

4.3、两整数之和

371. 两整数之和 – 力扣（LeetCode）

        算法思路

◦ 异或 ^ 运算本质是「⽆进位加法」；◦ 按位与 & 操作能够得到「进位」； ◦ 然后⼀直循环进⾏，直到「进位」变成 0 为⽌。        代码实现

class Solution {
public:
    int getSum(int a, int b) 
    {
        while(b)
        {
            int x=a^b;
            unsigned int carry=(unsigned int)(a&b)<<1;
            a=x;
            b=carry;
        }
        return a;
    }
};

4.4、只出现一次的数字Ⅱ

137. 只出现一次的数字 II – 力扣（LeetCode）

        题目描述

        算法思路

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

这样，我们通过 ret 的每⼀个⽐特位上的值，就可以将 ret 给还原出来。        代码实现        

class Solution {
public:
    int singleNumber(vector<int>& nums) 
    { 
        map<int,int> freq;
        for(auto e:nums)
        {
            freq[e]++;
        }
        int k=0;
        for(auto [first,second]:freq)
        {
            if(second==1)
            {
                k=first;
                break;
            }
        }
        return k;
    }
};

4.5、消失的两个数字

        题目描述

        算法思路：

本题就是 【丢失的数字】 + 【只出现一次的数字】 组合起来的题。

先将数组中的数和 [1, n + 2] 区间内的所有数「异或」在⼀起，问题就变成了：有两个数出现了「⼀次」，其余所有的数出现了「两次」。进⽽变成了  【只出现一次的数字】  这道题。

        代码实现

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) 
    {
        int sum=0;
        for(auto e:nums)
        {
            sum^=e;
        }
        for(int i=1;i<=nums.size()+2;i++)
        {
            sum^=i;
        }
        //此时sum就是我们要找的两个数字的异或
        int bitdex=0;
        for(int i=0;i<32;i++)
        {
            if((sum>>i&1)==1)
            {
                bitdex=i;
                break;
            }
        }
        int a=0,b=0;
        for(int i=1;i<=nums.size()+2;i++)
        {
            if(((1<<bitdex)&i))
            {
                a^=i;
            }
            else
            {
                b^=i;
            }
        }
        for(auto e:nums)
        {
            if((1<<bitdex)&e)
            {
                a^=e;
            }
            else
            {
                b^=e;
            }
        }
        return {a,b};
    }
};