leetcode201. Bitwise AND of Numbers Range

wapeyang 發(fā)布于2019-08-15 13:59 / 742人閱讀

摘要：題目要求給一個閉區(qū)間，對該閉區(qū)間的所有數(shù)字進行與運算。在計算機底層所有的十進制數(shù)都是以二進制數(shù)進行存儲的。因此，當(dāng)我們同時左移時，一定會有一個時刻，使得與相等。這意味著，從該位起前面的所有位數(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.

給一個閉區(qū)間[m,n]，對該閉區(qū)間的所有數(shù)字進行與（and）運算。
與預(yù)算是指 1 and 1 = 0, 1 and 0 = 0, 0 and 1 = 0, 0 and 0 = 0。
這里都是以二進制為基礎(chǔ)進行與運算。在計算機底層所有的十進制數(shù)都是以二進制數(shù)進行存儲的。寫這道題目之前需要先去了解十進制轉(zhuǎn)二進制以及未操作符>>,>>>和<<。

思路和代碼

其實可以想到，如果一個區(qū)間含有偶數(shù)，那么這個區(qū)間中一定有一個數(shù)，其二進制的末位為0，那么就意味著這些數(shù)在該位上的與運算結(jié)果一定為0。
計算完末位后，我們來計算倒數(shù)第二位的與運算。這就相當(dāng)于將[m, n]區(qū)間轉(zhuǎn)化為[m/2,n/2]區(qū)間，在該區(qū)間上我們再來判斷是否包含偶數(shù)。
在一番嘗試之后，我們會發(fā)現(xiàn)，如果一個區(qū)間[m,n]，當(dāng)m不等于n時，其中一定包含偶數(shù)，即該末位的和運算一定為0。
因此，當(dāng)我們同時左移m,n時，一定會有一個時刻，使得m與n相等。這意味著，從該位起前面的所有位數(shù)值均相等。它們進行任何與運算一定等于它們本身。我們可以直接將這些位的內(nèi)容添加到結(jié)果集開頭。

代碼如下：

    public int rangeBitwiseAnd(int m, int n) {
        if(m==n) return m;
        int count = 0;
        while(m>>= 1 ;
            n >>>= 1;
        }
        return m<<=count;
    }

優(yōu)化后代碼如下：

    public int rangeBitwiseAnd2(int m, int n) {
        if(m==n) return m;
        int count = 1;
        while(m>>= 1 ;
            n >>>= 1;
        }
        return m * count;
    }

想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號！將會不定期的發(fā)放福利哦~