LeetCode刷题笔记(九): 位运算

常用技巧(其中0s和1s分别表示只由0或1构成的二进制数字。)：

1
2
3

x ^ 0s = x      x & 0s = 0     x | 0s = x
x ^ 1s = ~x     x & 1s = x     x | 1s = 1s
x ^ x = 0       x & x = x      x | x = x

除此之外，n&(n-1)可以去除n的位级表示中最低的那一位，例如对于二进制表示11110100，减去1得到11110011，这两个数按位与得到11110000。n&(-n)可以得到n的位级表示中最低的那一位，例如对于二进制表示11110100，取负得到00001100，这两个数按位与得到00000100。

一、位运算基础问题

题目一：汉明距离
给定两个十进制数字，求它们二进制表示的汉明距离(Hamming distance，即不同位的个数)。

解答：

class Solution {
public:
    int hammingDistance(int x, int y) {
        int temp = x ^ y;
        int count = 0;
        while (temp > 0) {
            if (temp & 1)
                ++count;
            temp >>= 1;
        }
        return count;
    }
};

提示：异或运算的本质就是算有多少位不同的。

题目二：颠倒二进制位
给定一个十进制正整数，输出它在二进制下的翻转结果。

解答：

class Solution {
public:
    int reverseBits(int n) {
        int res = 0;
        for (int i = 0; i < 32; ++i) {
            res |= (n & 0x1) << (31 - i);
            n >>= 1;
        }
        return res;
    }
};

提示：使用左移和右移运算来对齐位数，使用或运算来实现”相加”。

题目三：只出现一次的数字
给定一个整数数组，这个数组里只有一个数次出现了一次，其余数字出现了两次，求这个只出现一次的数字。

解答：

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

提示：两个相同的数做异或运算结果为0，0和任何数做异或运算结果为那个数本身，根据这个的性质很好求解。

二、二进制特性

题目一：最大单词长度乘积
给定多个字母串，求其中任意两个字母串的长度乘积的最大值，且这两个字母串不能含有相同字母。

解答：

class Solution {
public:
    int maxProduct(vector<string>& words) {
        unordered_map<int, int> map;
        int max_len = 0;
        for (const string& word : words) {
            int mask = 0, word_len = word.length();
            for (char c : word) mask |= 1 << (c - 'a');
            map[mask] = max(map[mask], word_len);
            for (auto& [i, j] : map) {
                if ((mask & i) == 0)
                    max_len = max(max_len, map[mask] * j);
            }
        }
        return max_len;
    }
};

提示：主要是理解这个mask，用26位二进制来表示一个单词出现了哪些字母，同时可以用一个map来记录mask对应的单词最长长度，比如ab和aab会记录aab的长度。

题目二：比特位计数
给定一个非负整数n，求从0到n的所有数字的二进制表达中，分别有多少个1。

解答：

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> res(n + 1);
        for (int i = 0; i <= n; ++i) {
            res[i] = res[i >> 1] + (i & 1);
        }
        return res;
    }
};

提示：注意二进制的性质，乘以二时末尾只会多一个0，根据这个性质来求解。

三、练习

题目一：丢失的数字
给定一个包含[0, n]中n个数的数组nums，找出[0, n]这个范围内没有出现在数组中的那个数。

解答：

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

提示：本质上和找到只出现一次的数字是一道题。

题目二：交替位二进制数
给定一个正整数，检查它的二进制表示是否总是0、1交替出现：换句话说，就是二进制表示中相邻两位的数字永不相同。

解答：

class Solution {
public:
    bool hasAlternatingBits(int n) {
        int last = n & 1;
        while (n > 0) {
            n >>= 1;
            if ((n & 1) == last) return false;
            last = n & 1;
        }
        return true;
    }
};

提示：没啥好说的，挺简单的一道题。

题目三：数字的补数
对整数的二进制表示取反(0变1，1变0)后，再转换为十进制表示，可以得到这个整数的补数。

解答：

class Solution {
public:
    int findComplement(int num) {
        unsigned int res = 0;
        int i = 0;
        while ((num >> i) > 0) {
            bool last = (num >> i) & 1;
            res |= (!last) << (i++);
        }
        return res;
    }
};

提示：注意不能直接使用~运算，会变成负数。

题目四：只出现一次的数字 III
给定一个整数数组，这个数组里只有两个数次出现了一次，其余数字出现了两次，求这两个只出现一次的数字。

解答：

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        unsigned int xorAll = 0;
        for (int num : nums)
            xorAll ^= num;
        xorAll &= -xorAll;
        int a = 0, b = 0;
        for (int num : nums) {
            if (num & xorAll) a ^= num;
            else b ^= num;
        }
        return {a, b};
    }
};