位运算

1.常见位运算总结

常见的位运算有左移<<、右移>>、按位取反~、按位与&、按位或|、异或^ 。使用位运算尽量加括号以明确优先级。给二进制数的每一位从右往左从0开始编号。

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

   先把n右移x位，把第x位变成最低位，再按位与1，即 (n>>x)&1 。1的二进制是00000001，如果第x位是0，则结果为0，如果第x位是1，则结果为1。

   

2. 将一个数n的二进制表示的第x位修改成1。

   n = n|(1<<x)即 n |= (1<<x) 。1左移x位到指定位，使得1<<x的第x位是1，第x位左右两侧都是0，此时n按位或上1<<x，就会使n的第x位变成1而其它位不变。

   

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

   n = n&(~(1<<x))即 n &= (~(1<<x)) 。

   

4. 提取一个数n二进制表示中最右侧的1（最低位的1）。

   n & (-n)。由n按位取反再+1得 -n。

   

5. 去掉一个数n二进制表示中最右侧的1。

   n & (n-1)。n-1会使n的最低位的1变为0，其右侧的每一位0都变为1。

   

6. 异或的运算律

   异或相同为0，相异为1。异或等价于二进制无进位加法，即01+01为00，其中1+1不进位。

   a^a=0 、a^0=a 、交换律a^b = b^a 、结合律(a^b)^c = a^(b^c) 。消去律，若a^b = a^c，则b=c。

7. 位图

   一个int类型的变量，有32 bit位，每个bit位为0或1，可以借助每个bit位来表示某种信息，类似哈希表，但是比哈希表更节省空间。

2.判断字符是否唯一

如果astr的长度大于26，由鸽巢原理，一定有重复字符，返回false。创建一个int变量bitmap，建立字符与bit位的映射，如果字符出现了，bitmap对应的bit位变为1；如果字符重复出现，bitmap对应的bit位就是1。

class Solution {
public:
    bool isUnique(string astr)
    {
        if (astr.size() > 26)
            return false;
        
        //位图
        int bitmap = 0;
        for (auto& ch : astr)
        {
            int i = ch - 'a';//字符与bit位的映射
            if (((bitmap >> i) & 1) == 1)//判断字符是否出现过
                return false;
            bitmap |= (1 << i);//当前字符加入位图
        }
        return true;
    }
};

3.丢失的数字

根据异或的性质，a^a=0 、a^0=a ，以及异或满足交换律和结合律。

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

4.两整数之和

异或等价于二进制无进位加法，可以考虑用异或解决。例如13+28=41，13的二进制001101，28的二进制011100，41的二进制101001。令a=13，b=28，a^b = 010001，a+b = 101001，显然a^b是没有进位的。只有1+1才需要进位1，其余进位0，这就类似&，所以通过(a&b)<<1算出进位。把 a^b当成新的a，(a&b)<<1当成新的b，不断循环，当进位为0时，就得到a+b。

快速求二进制。从右往左列1，2，4，8，16，32……每个数下面为0，配凑13，13=8+4+1，对应数字下面记为1，此时数字序列即为13的二进制。

class Solution5 {
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;
    }
};

5.只出现一次的数字

nums中每个元素的每个bit位要么是0，要么是1，nums的元素个数为n，只出现一次的元素为a。nums中所有元素的某个bit位的和只能有4种情况，3n个0 + 0 = 0 ，3n个0 + 1 = 1，3n个1 + 0 = 3n，3n个1 + 1 = 3n+1。这些和模3的结果为0、1、0、1，即结果为0，则只出现一次的元素a对应的bit位是0，结果为1，a对应的bit位是1。由此能得到a的所有bit位，进而得到a。

题目可扩展为某个元素只出现1次，其余每个元素恰出现n次。此时对应模n即可。

class Solution {
public:
    int singleNumber(vector<int>& nums)
    {
        int ret = 0;
        for (int i = 0;i < 32;i++)//遍历nums每个元素的每一个bit位
        {
            int sum = 0;
            for (auto& e : nums)// 计算nums中所有数的第 i 位的和
                if (((e >> i) & 1) == 1)
                    sum++;
            sum %= 3;
            if (sum == 1)
                ret |= (1 << i);
        }
        return ret;
    }
};

6.消失的两个数字

根据题意，1~N与nums相比，1 ~N其余与nums一样，只多了两个数a，b，要求返回a，b。把1 ~N和nums的所有数异或，得到t，即t=a^b。

t中bit位为1的那一位，说明a和b在该位上是不同的，我们选t的最低位的1，在所有数中，在该位为0的数分在一起，在该位为1的数分在一起，这样就分开了a，b。相同的数也会分在一起，比如nums中的1和1 ~N中的1会分在一起，nums中的2和1 ~N中的2会一起分到另一部分，分别异或这两部分数字，即可得到a，b。

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums)
    {   //将所有数异或在一起
        int t = 0;
        for (auto& e : nums)
            t ^= e;
        for (int i = 1;i <= nums.size() + 2;i++)
            t ^= i;
		
        //找出 a，b 中bit位不同的那一位
        int diff = 0;
        while (1)
        {
            if (((t >> diff) & 1) == 1)
                break;
            else
                diff++;
        }
		
        //根据 diff 位的不同，将所有的数划分为两类来异或
        int a = 0, b = 0;
        for (auto& e : nums)
            if (((e >> diff) & 1) == 1)
                a ^= e;
            else
                b ^= e;
        for (int i = 1;i <= nums.size() + 2;i++)
            if (((i >> diff) & 1) == 1)
                a ^= i;
            else
                b ^= i;

        return { a,b };
    }
};