位运算的奇技淫巧

常见位运算总结：

1、基础位运算

左移<<运算

将二进制数向左移位操作，高位溢出则丢弃，低位补0。

右移>>运算

右移位运算中，无符号数和有符号数的运算并不相同。对于无符号数，右移之后高位补0；对于有符号数，符号位一起移动，正数高位补0，负数高位补1

按位与&运算

有0就是0，巧计：&这个符号像是有两个0组合而成。

按位或 | 运算

有1就是1，巧计：|本身就像一个1

按位异或^运算（两种解释方法）

相同为0，相异为1，或者解释成无进位相加。

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

(n >> x) & 1

&1后的结果就是0/1，因为1的二进制位除了最后一位，其他都是0，&0就是0

3、将一个数n的二进制位的第x位改成1

n =（1?<< x）| ?n

4、将一个数n的二进制位的第x位改成0

n = n & (~（1 << x）)

5、位图的思想

本质上就是一个哈希表

6、提取一个数（n）二进制表示中最右侧的1（lowbit）

n & -n

解释：-n的操作就是先取反，然后再+1，这样造成的影响是最右边的1前面都是n的相反数，这样再跟原先的n&，因为是相反数，所以有一方肯定是0，这样最右边的1前面的数字都变成了0，最右边1右边本身就是0。

7、干掉一个数（n）最右边的1

n &（n - 1）

8、位运算的优先级

为了避免记住闲杂的公式，我们只需要记住能加括号就加括号。

9、异或运算的运算规律

• a ^ 0 = a
• a ^ a = 0（消消乐）
• a ^ b ^ c = a ^ (b ^ c)

上面的指示是位运算的基础知识，下面就带着上面的指示开始实操啦

第一题：
191. 位1的个数

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明重量）。

解析：

只需要每次右移&1判断是否为1。

原码：

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int sum = 0;
        int ret = n;
        for(int i = 0;i<32;i++)
        {
            if(ret & 1 == 1) sum++;
            ret = ret >> 1;
        }
        return sum;
    }
};

第二题、461. 汉明距离

两个整数之间的?汉明距离?指的是这两个数字对应二进制位不同的位置的数目。

给你两个整数?x?和?y，计算并返回它们之间的汉明距离。

解析：

根据题目来看，可能最先想到的就是异或操作，相同为 0，不同为 1。异或操作后结果为?0101，然后我们只需要统计出来二进制结果中 1 的个数就可以计算出来汉明距离啦。

原码：

class Solution {
public:
    int hammingDistance(int x, int y) {
        int ret = x ^ y;
        int sum = 0;
        //计算1的个数
        for(int i = 0;i<32;i++)
        {
            if(ret & 1 == 1) sum++;
            ret = ret >> 1;
        } 
        return sum;
    }
};

第三题、136. 只出现一次的数字

给你一个?非空?整数数组?nums?，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

解析：

这是一道很典型的运用^的题目，我们只需要理解异或运算符，这题就迎刃而解啦。

原码：

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

第四题、260. 只出现一次的数字 III

给你一个整数数组?nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按?任意顺序?返回答案。

你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。

解析：

本题是上一题的升级版，

把nums中的元素全部异或起来的结果eor就是那两个只出现一次的数字的异或结果。而这两个数不相同，意味着eor至少有一位是1，我们可以用lowbit运算拿到最低位的1，然后遍历nums数组，将所有数nums[i]按照这一位是不是1分成两类，初始化num1=num2=0

1. 如果当前位是1，就将nums[i]异或到num1?上。

2. 如果当前位是0，就将nums[i]异或到num2?上。

这样一来，两个只出现一次的数就会被分别异或到num1?和num2?上，而其他数也会被分别异或到这两个数上。而由于其他数都出现了两次，所以最终它们就会被异或成0，num1?和num2?就是那两个只出现一次的数。

注意进行位运算的优先级，直接加上括号就好！！！

原码：

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int a = 0, b = 0;//记录两个不同的数
        int ret = 0;
        for(int i = 0;i<nums.size();i++)
            ret ^= nums[i];
        //进行lowbit运算，两者不同，二进制肯定有1
        int tmp = ret & (-(long long)ret);//防止数据溢出
        for(int i = 0;i<nums.size();i++)
        {
            if((tmp & nums[i]) == 0)//注意优先级！ 
                a ^= nums[i];
            else b ^= nums[i];
        }
        return {a,b};
    }
};

第五题、面试题 01.01. 判定字符是否唯一

解析：

本题第一思想直接用哈希表解决，但题目中用说尽量不用数据结构，我们可以尝试用位图解决!

用位图解决，需要熟练掌握位运算技巧，对巩固位运算有很大帮助！

原码：

class Solution {
public:
    bool isUnique(string astr) {
        int bitmap = 0;//用位图思想解决
        int tmp = 0;
        int n = astr.size();
        //利用鸽巢原理优化
        if(n > 26) return false;
        for(int i = 0;i<astr.size();i++)
        {
            tmp = astr[i] - 'a';
            //判断字符是否已经出现过
            if(((bitmap >> tmp) & 1) == 1) return false;
            //把当前字符加入位图中
            bitmap = bitmap | (1 << tmp);
        }
        return true;
    }
};

第六题、371. 两整数之和

给你两个整数?a?和?b?，不使用?运算符?+?和?-?，计算并返回两整数之和。

思路：

我们前面介绍了^运算的另一个功能是不进位相加，因此我们可以利用这个特性去解决这道题。

因为是不进位，所以我们要想办法去解决进位的问题，^运算是相同为0，相异为1，相异不可能进位，只有相同并且都是1的情况下，才会进位，因此我们直接&，查找出都是1，因为是进位，所以还要左移一位，（a & b）<< 1，然后分别重制a,b的值。

原码：

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

第七题、137. 只出现一次的数字 II

给你一个整数数组?nums?，除某个元素仅出现?一次?外，其余每个元素都恰出现?三次 。请你找出并返回那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

解析：

本题有点难度，两层嵌套循环，根据32位int，把每个数位相加再对3取的余数即可，将每个数想象成32位的二进制，对于每一位的二进制的1和0累加起来必然是3N或者3N+1， 为3N代表目标值在这一位没贡献，3N+1代表目标值在这一位有贡献(=1)，然后将所有有贡献的位|起来就是结果。这样做的好处是如果题目改成K个一样，只需要把代码改成cnt%k，很通用~

原码：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        int n = nums.size();
        for(int i = 0;i<32;i++)//依次去修改ans的每一位
        {
            int sum = 0;
            for(int j = 0;j<n;j++)
            {
                //计算nums中所有数的第i位的和
                sum += (nums[j] >> i) & 1;
            }
            //把第i位修改
            if(sum % 3)   
                ans ^= (1 << i); 
        }
        return ans;
    }
};

第八题、面试题 17.19. 消失的两个数字

给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？

以任意顺序返回这两个数字均可。

解析：

本题是两道题的融合版。

• 将所有的数异或在一起，记为tmp
• 找到tmp中，比特位上为1的那一位
• 根据不同的那一位，划分为两类异或

原码

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int a = 0,b = 0;
        int n = nums.size();
        int ret = 0;
        //先将所有数异或
        for(int i = 1;i<=n+2;i++)
            ret ^= i;
        for(int i = 0;i<n;i++)
            ret ^= nums[i];
        //lowbit运算找到最右边的1
        int tmp = ret & (-(long long)ret);//防止溢出
        for(int i = 0;i<n;i++)
        {
            if((nums[i] & tmp) == 0) a ^= nums[i];
            else b ^= nums[i];
        }
        for(int i = 1;i<=n+2;i++)
        {
            if((i & tmp) == 0) a ^= i;
            else b ^= i; 
        }
        return {a,b};
    }
};