leetcode201. Bitwise AND of Numbers Range

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

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

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

思路和代碼

其實(shí)可以想到，如果一個(gè)區(qū)間含有偶數(shù)，那么這個(gè)區(qū)間中一定有一個(gè)數(shù)，其二進(jìn)制的末位為0，那么就意味著這些數(shù)在該位上的與運(yùn)算結(jié)果一定為0。
計(jì)算完末位后，我們來計(jì)算倒數(shù)第二位的與運(yùn)算。這就相當(dāng)于將[m, n]區(qū)間轉(zhuǎn)化為[m/2,n/2]區(qū)間，在該區(qū)間上我們?cè)賮砼袛嗍欠癜紨?shù)。
在一番嘗試之后，我們會(huì)發(fā)現(xiàn)，如果一個(gè)區(qū)間[m,n]，當(dāng)m不等于n時(shí)，其中一定包含偶數(shù)，即該末位的和運(yùn)算一定為0。
因此，當(dāng)我們同時(shí)左移m,n時(shí)，一定會(huì)有一個(gè)時(shí)刻，使得m與n相等。這意味著，從該位起前面的所有位數(shù)值均相等。它們進(jìn)行任何與運(yùn)算一定等于它們本身。我們可以直接將這些位的內(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)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~