面试官，你再问我 Bit Operation 试试？

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

在这些题目中，位操作（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 cnt = 0;
        while(n > 0){
            cnt++;
            n = n & (n - 1);
        }
        return cnt;
    }
};
题目二：2 的幂

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

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

表格

仔细观察，可以看出 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。

图 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 ] 的范围数字用二进制表示出来：

11010　　11011　　11100　　11101　　11110

而输出 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 序列