面试官，别问我 Bit Operation 了！

深碍√TFBOYSˉ_ 2022-03-17 07:46 315阅读 0赞

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

在面试环节中，面试官很喜欢问一些特别的题目，这些题目有着特殊的解法，如果回答的巧妙往往能在面试中加分。

在这些题目中，位操作（Bit Operation）就是极具魅力的一种。今天，吴师兄就来分享 LeetCode 上几道跟 Bit Operation 有关的题目。

### 题目一： 位 1 的个数 ###

LeetCode上第 191 号问题：编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数。

该题比较简单，解法有挺多，有位移法、位操作法、查表法、二次查表法等方法。

观察一下 n 与 n-1 这两个数的二进制表示：对于 n-1 这个数的二进制来说，相对于 n 的二进制，它的最末位的一个 1 会变成 0，最末位一个 1 之后的 0 会全部变成 1，其它位相同不变。

比如 n = 8888，其二进制为 **10001010111000**

则 n - 1 = 8887 ，其二进制为 **10001010110111**

通过按位与操作后：n **&** (n-1) = **10001010110000**

也就是说：通过 **n&(n-1)这个操作**，可以起到**消除最后一个1**的作用。

所以可以通过执行 n&(n-1) 操作来消除 n 末尾的 1 ，消除了多少次，就说明有多少个 1 。

代码如下：

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

### 题目二：2 的幂 ###

LeetCode上第 231 号问题：给定一个整数，编写一个函数来判断它是否是 2 的幂次方。

首先，先来分析一下 2 的次方数的二进制写法：

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1] 表格

仔细观察，可以看出 2 的次方数都只有一个 1 ，剩下的都是 0 。根据这个特点，只需要每次判断最低位是否为 1 ，然后向右移位，最后统计 1 的个数即可判断是否是 2 的次方数。

代码很简单：

class Solution {
         
    public:
        bool isPowerOfTwo(int n) {
        
            int cnt = 0;
            while (n > 0) {
        
                cnt += (n & 1);
                n >>= 1;
            }
            return cnt == 1;
        } 
    };

该题还有一种巧妙的解法。再观察上面的表格，如果一个数是 2 的次方数的话，那么它的二进数必然是最高位为1，其它都为 0 ，那么如果此时我们减 1 的话，则最高位会降一位，其余为 0 的位现在都为变为 1，那么我们把两数相与，就会得到 0。

比如 2 的 3 次方为 8，二进制位 1000 ，那么 `8 - 1 = 7`，其中 7 的二进制位 0111。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 2] 图 2

利用这个性质，只需一行代码就可以搞定。

class Solution {
         
    public:
        bool isPowerOfTwo(int n) {
        
            return (n > 0) && (!(n & (n - 1)));
        } 
    };

### 题目三：数字范围按位与 ###

LeetCode上第 201 号问题：给定范围 \[m, n\]，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）。

**示例 :**

输入: [26,30]
    输出: 24

首先，将 \[ 26 , 30 \] 的范围数字用二进制表示出来：

**11**010　　**11**011　　**11**100　　**11**101　　**11**110

而输出 24 的二进制是 11000 。

可以发现，只要找到二进制的 **左边公共部分** 即可。

所以，可以先建立一个 32 位都是 1 的 mask，然后每次向左移一位，比较 m 和 n 是否相同，不同再继续左移一位，直至相同，然后把 m 和 mask 相与就是最终结果。

class Solution {
         
    public:
        int rangeBitwiseAnd(int m, int n) {
        
            int d = INT_MAX;
            while ((m & d) != (n & d)) {
        
                d <<= 1;
            }
            return m & d;
        }
    };

### 题目四：重复的 DNA 序列 ###

LeetCode上第 187 号问题：所有 DNA 由一系列缩写为 A，C，G 和 T 的核苷酸组成，例如：“ACGAATTCCG”。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。

编写一个函数来查找 DNA 分子中所有出现超过一次的 10 个字母长的序列（子串）。

**示例:**

输入: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
    
    输出: ["AAAAACCCCC", "CCCCCAAAAA"]

首先，依旧先将 A , C , G , T 的 ASCII 码用二进制来表示：

A: 0100 0**001**　　C: 0100 0**011**　　G: 0100 0**111**　　T: 0101 0**100**

通过观察发现每个字符的后三位都不相同，因此可以用**末尾的三位**来区分这四个字符。

题目要求是查找 10 个字母长的序列，这里我们将每个字符用三位来区分的话，10 个字符就需要 30 位 ，在32位机上也 OK 。

为了提取出后 30 位，需要使用 **mask** ，取值为 0x7ffffff（二进制表示含有 27 个 1） ，先用此 mask 可取出**整个序列**的后 27 位，然后再向左平移三位可取出 10 个字母长的序列 （ 30 位）。

为了保存子串的频率，这里使用**哈希表**。

首先当取出第十个字符时，将其存在哈希表里，和该字符串出现频率映射，之后每向左移三位替换一个字符，查找新字符串在哈希表里出现次数，如果之前刚好出现过一次，则将当前字符串存入返回值的数组并将其出现次数加一，如果从未出现过，则将其映射到 1。

举个?：

根据题意，第一个操作：首先取出前九个字符 AAAAACCCC ，根据上面的分析，用三位来表示一个字符，所以这九个字符可以用二进制表示为 001001001001001011011011011，

第二个操作：开始遍历字符串，下一个进来的是 C ，则当前字符为 AAAAACCCCC ，二进制表示为001001001001001011011011011011，然后将其存入哈希表中。然后再读入下一个字符 A，则此时字符串为AAAACCCCCA，依旧使用二进制进行表示。

以此类推，当某个序列之前已经出现过了，只需要将其存入结果 res 中即可，参见代码如下：

class Solution {
         
    public:
        vector<string> findRepeatedDnaSequences(string s) {
        
            vector<string> res;
            if (s.size() <= 10) return res;
            int mask = 0x7ffffff, cur = 0;
            unordered_map<int, int> m;
            for (int i = 0; i < 9; ++i) {
        
                cur = (cur << 3) | (s[i] & 7);
            }
            for (int i = 9; i < s.size(); ++i) {
        
                cur = ((cur & mask) << 3) | (s[i] & 7);
                if (m.count(cur)) {
        
                    if (m[cur] == 1) res.push_back(s.substr(i - 9, 10));
                    ++m[cur]; 
                } else {
        
                    m[cur] = 1;
                }
            }
            return res;
        }
    };

如果你看过我前文的 [**算法科普：有趣的霍夫曼编码**][Link 1]，肯定会思考能不能用更简单的字符进行表示。

答案是可以的！

上面的方法都是用三位来表示一个字符，由于这里只有四个不同的字母，用两位来表示一个字符也是可以满足需要的。

00 表示 A ，01 表示 C ，10 表示G ，11 表示T ，这样的话总共需要20位就可以表示十个字符流，其余的思路跟上面的方法完全相同，只需要将 mask 修改为 0x3ffff （二进制表示含有 18 个 1）即可。

class Solution {
         
    public:
        vector<string> findRepeatedDnaSequences(string s) {
        
            unordered_set<string> res;
            unordered_set<int> st;
            unordered_map<int, int> m{
        {
        'A', 0}, {
        'C', 1}, {
        'G', 2}, {
        'T', 3}};
            int cur = 0;
            for (int i = 0; i < 9; ++i) cur = cur << 2 | m[s[i]];
            for (int i = 9; i < s.size(); ++i) {
        
                cur = ((cur & 0x3ffff) << 2) | (m[s[i]]);
                if (st.count(cur)) res.insert(s.substr(i - 9, 10));
                else st.insert(cur);
            }
            return vector<string>(res.begin(), res.end());
        }
    };

### End ###

除了上面这四道跟 Bit Operation 有关的题目外，LeetCode 上的还有很多题目也和位操作有关，比如 **格雷码**、**翻转位**、**两数相除** 等等。

当然，之前写过的那篇 [**一道让你拍案叫绝的算法题**][Link 2] 也是 Bit Operation 的经典操作。

本文完。

--------------------