我爱学算法之—— 位运算（上）

常见位运算

对于位运算：

&：按位与，有0则0。

|：按位或，有1则1。

^：按位异或，相同为0、不同为1。（无进位相加）

~：二进制位按位取反。

对于位运算的常见使用：

1. 判断一个数n，二进制中第x位是0还是1

例如一个数n：01001101，要判断第4位是0还是1（从低位数）

就可让01001101 按位与上00001000，这样如果第4位为0，结果就是0；如果第4位为1，结果就是1。

所以，就可以判断**(n>>x) & 1**，结果为1就表示第x为1；结果为0则表示第x位为0。

2. 将一个数n，二进制第x位修改为1

例如一个数n：01100100，要将第4位修改为1

就可以让01100100按位或上00001000，这里无论第4位是0还是1，结果都是1；而其他位异或上0都不变（1 | 0 = 1、0 | 0 = 0）。

而00001000只需让1左移3位即可。

所以，修改二进制第x位1，只需：n | (1<<x)

3. 将一个数n，二进制第x位修改为0

例如一个数n：00101100，将第4位修改为0

就可以让00101100按位与上11110111；这样无论第4位是什么，结果都为1，而其他位按位与上1都不变（1 & 1 = 1、0 & 1 = 0）

而11110111，只需要让1左移4位，然后按位取反即可。

4. 位图

对于位图，简单来说就是使用一个bit位来表示状态（0和1）

5. 提取一个数n二进制中最右侧的1

要提取一个数n二进制中最右侧的1，只需要n & (-n)即可。

例如：n：01100100，而-n的补码（原码取反加一）：10011011（取反）、10011100（加一）

通过观察，取反加一，就是最右侧的1的右侧不变，左侧取反。（右侧为0），再按位与即可提取最右侧的1。

01100100 & 10011011结果就等于00000100；

6. 去掉一个数n二进制中最右侧的1

有去掉一个数n二进制中最右侧的1，只需要n & (n-1)即可

例如n ： 01011000，而n-1 : 01010111

通过观察，n-1本质就是让n最右侧1的右侧取反（由全0变全1），左侧不变；

再按位与，右侧结果都为0（和n一样）；而左侧没有变化。

01011000 & 01010111 结果为01010000。

7. 按位异或

对于按位异或，常见的使用：

1. n ^ n = 0
2. n ^ 0 = n
3. a ^ b ^ c = a ^ (b ^ c)（支持交换律）

一、位1的个数

对于这道题，要获取一个数n二进制中设置位的个数（1的个数）

而我们可以通过n & (n - 1)的操作来去掉n二进制中最后的1，所以，就可以对n一直进行n = n & (n - 1)操作，直到n为0。

而n &= (n - 1)的次数就是数n二进制中1的个数。

class Solution {
public:
    int hammingWeight(int n) {
        int ret = 0;
        while (n) {
            n &= (n - 1);
            ret++;
        }
        return ret;
    }
};

二、比特位计数

这道题，给定一个n要求，返回一个数组ans，ans中存储的是[0 , n]之间每个数二进制形式中1的个数。

简单来说就是，获取[0,n]中每个数二进制中1的个数。

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> ans;
        for (int i = 0; i <= n; i++) {
            int tmp = i;
            int cnt = 0;
            while (tmp) {
                tmp &= (tmp - 1);
                cnt++;
            }
            ans.push_back(cnt);
        }
        return ans;
    }
};

三、汉明距离

对于这道题，给两个数x、y，要求x和y的汉明距离（二进制中不同位的数目）

简单来说就是求x与y二进制中，不同bit位置的数目。

解题思路：

我们知道^操作，相同为0，不同为1；所以，x ^ y二进制中为1就表示x和y该bit为不相同。

只需要判断x^y的二进制中1的个数即可。

class Solution {
public:
    int hammingDistance(int x, int y) {
        int tmp = x ^ y;
        int ret = 0;
        while (tmp) {
            tmp &= (tmp - 1);
            ret++;
        }
        return ret;
    }
};

四、只出现一次的数字

这道题，给定一个非空的数组nums，其他有一个元素只出现了一次，其他元素都出现了两次。

^操作：

• n ^ 0 = n
• n ^ n = 0

这里只需要将nums中所有元素都进行^即可，最终的结果就是只出现一次的元素（其他所有元素都出现了两次，^结果为0。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        for (auto& e : nums) {
            ret ^= e;
        }
        return ret;
    }
};

五、只出现一次的数字 III

这道题给定一个数组nums，其中存在两个元素只出现了一次，其他所有的元素都出现了两次；

这里要我们返回这两个主出现了一次的元素。

解法一：

使用hash表统计数组中的元素和出现的次数；最后找出只出现一次的两个元素，然后返回。

解法二：

假设只出现的元素为x和y，将数组中的所有元素进行^，最终结果为：x ^ y。

• 提取x ^ y二进制bit位最低位的1：lowbit；
• (x ^ y)该bit位为1，x和y该bit位不相同（通过该bit位将x和y区分开）
• 再遍历nums数组，lowbit位1的为一组，lowbit位0的为一组（x和y一定不在同一组）。
• 获取x和y，然后返回

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int n = 0;
        for (auto& e : nums)
            n ^= e;
        int lowbit = (n == INT_MIN ? n : n & -n);
        vector<int> ret(2, 0);
        for (auto& e : nums) {
            if (e & lowbit) // 1
                ret[0] ^= e;
            else
                ret[1] ^= e;
        }
        return ret;
    }
};

我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=2oul0hvapjsws