在面試環(huán)節(jié)中，面試官很喜歡問一些特別的題目，這些題目有著特殊的解法，如果回答的巧妙往往能在面試中加分。
在這些題目中，位操作（Bit Operation）就是極具魅力的一種。今天，吳師兄就來分享 LeetCode 上幾道跟 Bit Operation 有關(guān)的題目。
LeetCode上第 191 號(hào)問題：編寫一個(gè)函數(shù)，輸入是一個(gè)無符號(hào)整數(shù)，返回其二進(jìn)制表達(dá)式中數(shù)字位數(shù)為 ‘1’ 的個(gè)數(shù)。
該題比較簡單，解法有挺多，有位移法、位操作法、查表法、二次查表法等方法。
觀察一下 n 與 n-1 這兩個(gè)數(shù)的二進(jìn)制表示：對于 n-1 這個(gè)數(shù)的二進(jìn)制來說，相對于 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;
}
};
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ù)。
代碼很簡單：
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。
利用這個(gè)性質(zhì)，只需一行代碼就可以搞定。
class Solution {
public:
bool isPowerOfTwo(int n) {
return (n > 0) && (!(n & (n - 1)));
}
};
LeetCode上第 201 號(hào)問題：給定范圍 [m, n]，其中 0 <= m=""><= n=""><= 2147483647，返回此范圍內(nèi)所有數(shù)字的按位與（包含="" m,="" 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;
}
};
LeetCode上第 187 號(hào)問題：所有 DNA 由一系列縮寫為 A，C，G 和 T 的核苷酸組成，例如：“ACGAATTCCG”。在研究 DNA 時(shí)，識(shí)別 DNA 中的重復(fù)序列有時(shí)會(huì)對研究非常有幫助。
編寫一個(gè)函數(shù)來查找 DNA 分子中所有出現(xiàn)超過一次的 10 個(gè)字母長的序列（子串）。
示例:
輸入: 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è)字母長的序列，這里我們將每個(gè)字符用三位來區(qū)分的話，10 個(gè)字符就需要 30 位 ，在32位機(jī)上也 OK 。
為了提取出后 30 位，需要使用 mask ，取值為 0x7ffffff（二進(jìn)制表示含有 27 個(gè) 1） ，先用此 mask 可取出整個(gè)序列的后 27 位，然后再向左平移三位可取出 10 個(gè)字母長的序列 （ 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:
vectorstring> findRepeatedDnaSequences(string s) {
vectorstring> res;
if (s.size() <>10) return res;
int mask = 0x7ffffff, cur = 0;
unordered_mapint, int> m;
for (int i = 0; i <>9; ++i) {
cur = (cur <>3) | (s[i] & 7);
}
for (int i = 9; 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;
}
};
如果你看過我前文的 算法科普：有趣的霍夫曼編碼，肯定會(huì)思考能不能用更簡單的字符進(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:
vectorstring> findRepeatedDnaSequences(string s) {
unordered_setstring> res;
unordered_setint> st;
unordered_mapint, 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 <>
cur = ((cur & 0x3ffff) <>2) | (m[s[i]]);
if (st.count(cur)) res.insert(s.substr(i - 9, 10));
else st.insert(cur);
}
return vectorstring>(res.begin(), res.end());
}
};
除了上面這四道跟 Bit Operation 有關(guān)的題目外，LeetCode 上的還有很多題目也和位操作有關(guān)，比如 格雷碼、翻轉(zhuǎn)位、兩數(shù)相除 等等。
當(dāng)然，之前寫過的那篇 一道讓你拍案叫絕的算法題 也是 Bit Operation 的經(jīng)典操作。
本文完。
聯(lián)系客服
