在面試中，面試官喜歡問有特殊解法的特殊問題。如果回答巧妙，面試中往往會(huì)加分。(大衛(wèi)亞設(shè))。

在這些題目中，位操作（Bit Operation）就是極具魅力的一種。今天，吳師兄就來分享 LeetCode 上幾道跟 Bit Operation 有關(guān)的題目。

題目一： 位 1 的個(gè)數(shù)

LeetCode上第 191 號(hào)問題：編寫一個(gè)函數(shù)，輸入是一個(gè)無符號(hào)整數(shù)，返回其二進(jìn)制表達(dá)式中數(shù)字位數(shù)為 ‘1’ 的個(gè)數(shù)。

該題比較簡(jiǎn)單，解法有挺多，有位移法、位操作法、查表法、二次查表法等方法。

觀察一下 n 與 n-1 這兩個(gè)數(shù)的二進(jìn)制表示：對(duì)于 n-1 這個(gè)數(shù)的二進(jìn)制來說，相對(duì)于 n 的二進(jìn)制，它的最末位的一個(gè) 1 會(huì)變成 0，最末位一個(gè) 1 之后的 0 會(huì)全部變成 1，其它位相同不變。

比如 n = 8888，其二進(jìn)制為 10001010111000

則 n - 1 = 8887 ，其二進(jìn)制為 10001010110111

通過按位與操作后：n & (n-1) = 10001010110000

也就是說：通過 n&(n-1)這個(gè)操作，可以起到消除最后一個(gè)1的作用。

所以可以通過執(zhí)行 n&(n-1) 操作來消除 n 末尾的 1 ，消除了多少次，就說明有多少個(gè) 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 號(hào)問題：給定一個(gè)整數(shù)，編寫一個(gè)函數(shù)來判斷它是否是 2 的冪次方。

首先，先來分析一下 2 的次方數(shù)的二進(jìn)制寫法：

表格

仔細(xì)觀察，可以看出 2 的次方數(shù)都只有一個(gè) 1 ，剩下的都是 0 。根據(jù)這個(gè)特點(diǎn)，只需要每次判斷最低位是否為 1 ，然后向右移位，最后統(tǒng)計(jì) 1 的個(gè)數(shù)即可判斷是否是 2 的次方數(shù)。

代碼很簡(jiǎn)單：

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

該題還有一種巧妙的解法。再觀察上面的表格，如果一個(gè)數(shù)是 2 的次方數(shù)的話，那么它的二進(jìn)數(shù)必然是最高位為1，其它都為 0 ，那么如果此時(shí)我們減 1 的話，則最高位會(huì)降一位，其余為 0 的位現(xiàn)在都為變?yōu)?1，那么我們把兩數(shù)相與，就會(huì)得到 0。

比如 2 的 3 次方為 8，二進(jìn)制位 1000 ，那么 8 - 1 = 7，其中 7 的二進(jìn)制位 0111。

圖 2

利用這個(gè)性質(zhì)，只需一行代碼就可以搞定。

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

題目三：數(shù)字范圍按位與

LeetCode上第 201 號(hào)問題：給定范圍 [m, n]，其中 0 <= m <= n <= 2147483647，返回此范圍內(nèi)所有數(shù)字的按位與（包含 m, n 兩端點(diǎn)）。

示例 :

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

首先，將 [ 26 , 30 ] 的范圍數(shù)字用二進(jìn)制表示出來：

11010 11011 11100 11101 11110

而輸出 24 的二進(jìn)制是 11000 。

可以發(fā)現(xiàn)，只要找到二進(jìn)制的 左邊公共部分 即可。

所以，可以先建立一個(gè) 32 位都是 1 的 mask，然后每次向左移一位，比較 m 和 n 是否相同，不同再繼續(xù)左移一位，直至相同，然后把 m 和 mask 相與就是最終結(jié)果。

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

題目四：重復(fù)的 DNA 序列

LeetCode上第 187 號(hào)問題：所有 DNA 由一系列縮寫為 A，C，G 和 T 的核苷酸組成，例如：“ACGAATTCCG”。在研究 DNA 時(shí)，識(shí)別 DNA 中的重復(fù)序列有時(shí)會(huì)對(duì)研究非常有幫助。

編寫一個(gè)函數(shù)來查找 DNA 分子中所有出現(xiàn)超過一次的 10 個(gè)字母長(zhǎng)的序列（子串）。

示例:

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

首先，依舊先將 A , C , G , T 的 ASCII 碼用二進(jìn)制來表示：

A: 0100 0001 C: 0100 0011 G: 0100 0111 T: 0101 0100

通過觀察發(fā)現(xiàn)每個(gè)字符的后三位都不相同，因此可以用末尾的三位來區(qū)分這四個(gè)字符。

題目要求是查找 10 個(gè)字母長(zhǎng)的序列，這里我們將每個(gè)字符用三位來區(qū)分的話，10 個(gè)字符就需要 30 位 ，在32位機(jī)上也 OK 。

為了提取出后 30 位，需要使用 mask ，取值為 0x7ffffff（二進(jìn)制表示含有 27 個(gè) 1） ，先用此 mask 可取出整個(gè)序列的后 27 位，然后再向左平移三位可取出 10 個(gè)字母長(zhǎng)的序列 （ 30 位）。

為了保存子串的頻率，這里使用哈希表。

首先當(dāng)取出第十個(gè)字符時(shí)，將其存在哈希表里，和該字符串出現(xiàn)頻率映射，之后每向左移三位替換一個(gè)字符，查找新字符串在哈希表里出現(xiàn)次數(shù)，如果之前剛好出現(xiàn)過一次，則將當(dāng)前字符串存入返回值的數(shù)組并將其出現(xiàn)次數(shù)加一，如果從未出現(xiàn)過，則將其映射到 1。

舉個(gè)：

根據(jù)題意，第一個(gè)操作：首先取出前九個(gè)字符 AAAAACCCC ，根據(jù)上面的分析，用三位來表示一個(gè)字符，所以這九個(gè)字符可以用二進(jìn)制表示為 001001001001001011011011011，

第二個(gè)操作：開始遍歷字符串，下一個(gè)進(jìn)來的是 C ，則當(dāng)前字符為 AAAAACCCCC ，二進(jìn)制表示為001001001001001011011011011011，然后將其存入哈希表中。然后再讀入下一個(gè)字符 A，則此時(shí)字符串為AAAACCCCCA，依舊使用二進(jìn)制進(jìn)行表示。

以此類推，當(dāng)某個(gè)序列之前已經(jīng)出現(xiàn)過了，只需要將其存入結(jié)果 res 中即可，參見代碼如下：

class Solution { public: vector<string> findRepeatedDnaSequences(string s) { vector<string> res; if () <= 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 (cur)) { if (m[cur] == 1) res.push_back(i - 9, 10)); ++m[cur]; } else { m[cur] = 1; } } return res; } };

如果你看過我前文的

算法科普：有趣的霍夫曼編碼

，肯定會(huì)思考能不能用更簡(jiǎn)單的字符進(jìn)行表示。

答案是可以的！

上面的方法都是用三位來表示一個(gè)字符，由于這里只有四個(gè)不同的字母，用兩位來表示一個(gè)字符也是可以滿足需要的。

00 表示 A ，01 表示 C ，10 表示G ，11 表示T ，這樣的話總共需要20位就可以表示十個(gè)字符流，其余的思路跟上面的方法完全相同，只需要將 mask 修改為 0x3ffff （二進(jìn)制表示含有 18 個(gè) 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 (cur)) res.insert(i - 9, 10)); else (cur); } return vector<string>(), res.end()); } };

End

除了上面這四道跟 Bit Operation 有關(guān)的題目外，LeetCode 上的還有很多題目也和位操作有關(guān)，比如 格雷碼、翻轉(zhuǎn)位、兩數(shù)相除 等等。

當(dāng)然，之前寫過的那篇 一道讓你拍案叫絕的算法題 也是 Bit Operation 的經(jīng)典操作。

本文完。

---

推薦閱讀：

一道讓你拍案叫絕的算法題

算法科普：有趣的霍夫曼編碼

今日問題：

通過本篇文章，你知道了求解位 1 的個(gè)數(shù)有哪幾種解法？