面试官,别问我 Bit Operation 了! 深碍√TFBOYSˉ_ 2022-03-17 07:46 268阅读 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 的经典操作。 本文完。 -------------------- 推荐阅读: [一道让你拍案叫绝的算法题][Link 2] [算法科普:有趣的霍夫曼编码][Link 1] **今日问题:** 通过本篇文章,你知道了求解位 1 的个数有哪几种解法? **打卡格式:** 打卡 X 天,答:xxx 。 ![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 3] **欢迎关注这个会做动画的程序员?** 喜欢就点击“好看”吧! [640_wx_fmt_jpeg]: /images/20220317/1af9cb0fa527484dafbf82d6ce751f73.png [640_wx_fmt_jpeg 1]: /images/20220317/b5400d1eaa06458a8998b0168c253f28.png [640_wx_fmt_jpeg 2]: /images/20220317/86998684761243f4ba0e2058793385a0.png [Link 1]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484723&idx=1&sn=bf599e73765a1348866539417be80832&chksm=fa0e6ab2cd79e3a4cf3e33aace8c5f7b98f089ea1500b7cb09259ad2e553d709dca91264aa2d&scene=21#wechat_redirect [Link 2]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484505&idx=1&sn=4c1c056dd4852c3b4b1ead51c90a9b2d&chksm=fa0e6bd8cd79e2ce8188dcdd8843a5d071248906bfb8971c62d513dbd69b816acc191a78e4b2&scene=21#wechat_redirect [640_wx_fmt_jpeg 3]: /images/20220317/90cc7a3fbade45499a18ec7d8123357d.png
还没有评论,来说两句吧...