[LeetCode] 201.Bitwise AND of Numbers Range 數(shù)字范圍位相與

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

For example, given the range [5, 7], you should return 4.

Credits:
Special thanks to @amrsaqr for adding this problem and creating all test cases.

又是一道考察位操作Bit Operation的題，相似的題目在LeetCode中還真不少，比如Repeated DNA Sequences 求重復(fù)的DNA序列， Single Number 單獨的數(shù)字,   Single Number II 單獨的數(shù)字之二 ， Grey Code 格雷碼，和 Reverse Bits 翻轉(zhuǎn)位 等等，那么這道題其實并不難，我們先從題目中給的例子來分析，[5, 7]里共有三個數(shù)字，分別寫出它們的二進制為：

101　　110　　111

相與后的結(jié)果為100，仔細觀察我們可以得出，最后的數(shù)是該數(shù)字范圍內(nèi)所有的數(shù)的左邊共同的部分，如果上面那個例子不太明顯，我們再來看一個范圍[26, 30]，它們的二進制如下：

11010　　11011　　11100　　11101　　11110

發(fā)現(xiàn)了規(guī)律后，我們只要寫代碼找到左邊公共的部分即可，我們可以從建立一個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;
    }
};

此題還有另一種解法，不需要用mask，直接平移m和n，每次向右移一位，直到m和n相等，記錄下所有平移的次數(shù)i，然后再把m左移i位即為最終結(jié)果，代碼如下：

解法二：

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int i = 0;
        while (m != n) {
            m >>= 1;
            n >>= 1;
            ++i;
        }
        return (m << i);
    }
};

下面這種方法有點叼，就一行搞定了，通過遞歸來做的，如果n大于m，那么就對m和n分別除以2，并且調(diào)用遞歸函數(shù)，對結(jié)果再乘以2，一定要乘回來，不然就不對了，就舉一個最簡單的例子，m = 10, n = 11，注意這里是二進制表示的，然后各自除以2，都變成了1，調(diào)用遞歸返回1，這時候要乘以2，才能變回10，參見代碼如下：

解法三：

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        return (n > m) ? (rangeBitwiseAnd(m / 2, n / 2) << 1) : m;
    }
};

下面這種方法也不錯，也很簡單，如果m小于n就進行循環(huán)，n與上n-1，那么為什么要這樣與呢，舉個簡單的例子唄，110與上(110-1)，得到100，這不就相當(dāng)于去掉最低位的1么，n就這樣每次去掉最低位的1，如果小于等于m了，返回此時的n即可，參見代碼如下：

解法四：

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

參考資料：

https://discuss.leetcode.com/topic/13508/one-line-c-solution

https://discuss.leetcode.com/topic/12133/bit-operation-solution-java

https://discuss.leetcode.com/topic/20176/2-line-solution-with-detailed-explanation

到此這篇關(guān)于C++實現(xiàn)LeetCode(201.數(shù)字范圍位相與)的文章就介紹到這了,更多相關(guān)C++實現(xiàn)數(shù)字范圍位相與內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論