leetcode201. Bitwise AND of Numbers Range

wapeyang 發布于2019-08-15 13:59 / 734人閱讀

摘要：題目要求給一個閉區間，對該閉區間的所有數字進行與運算。在計算機底層所有的十進制數都是以二進制數進行存儲的。因此，當我們同時左移時，一定會有一個時刻，使得與相等。這意味著，從該位起前面的所有位數值均相等。

題目要求

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.

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

思路和代碼

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

代碼如下：

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

優化后代碼如下：

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

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

GPU云服務器云服務器

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/68437.html

[LeetCode] 628. Maximum Product of Three Numbers

Problem Given an integer array, find three numbers whose product is maximum and output the maximum product. Example 1:Input: [1,2,3]Output: 6Example 2:Input: [1,2,3,4]Output: 24Note:The length of the ...

jindong 2019-08-16 13:39 評論0 收藏0
Python基礎練習100題 ( 71~ 80）

摘要：刷題繼續昨天和大家分享了題，今天繼續來刷題解法一解法二解法一解法一解法二解法一解法一解法二解法一解法一解法二解法一解法二解法一解法二解法三解法一解法二源代碼下載這十道題的代碼在我的上，如果大家想看一下每道題的輸出結果，可以點擊以下鏈接下刷題繼續昨天和大家分享了61-70題，今天繼續來刷71~80題 Question 71: Please write a program to out...

Jeff 2019-07-31 10:31 評論0 收藏0
[LeetCode] 724. Find Pivot Index

Problem Given an array of integers nums, write a method that returns the pivot index of this array. We define the pivot index as the index where the sum of the numbers to the left of the index is equa...

vibiu 2019-08-16 13:49 評論0 收藏0
LeetCode 167：兩數之和 II - 輸入有序數組 Two Sum II - Input a

摘要：公眾號愛寫給定一個已按照升序排列的有序數組，找到兩個數使得它們相加之和等于目標數。函數應該返回這兩個下標值和，其中必須小于。示例輸入輸出解釋與之和等于目標數。公眾號：愛寫bug（ID：icodebugs）給定一個已按照升序排列的有序數組，找到兩個數使得它們相加之和等于目標數。函數應該返回這兩個下標值 index1 和 index2，其中 index1 必須小于 index2。...

張春雷 2019-08-16 18:29 評論0 收藏0
LeetCode 167：兩數之和 II - 輸入有序數組 Two Sum II - Input a

摘要：公眾號愛寫給定一個已按照升序排列的有序數組，找到兩個數使得它們相加之和等于目標數。函數應該返回這兩個下標值和，其中必須小于。示例輸入輸出解釋與之和等于目標數。公眾號：愛寫bug（ID：icodebugs）給定一個已按照升序排列的有序數組，找到兩個數使得它們相加之和等于目標數。函數應該返回這兩個下標值 index1 和 index2，其中 index1 必須小于 index2。...

Me_Kun 2019-07-31 11:26 評論0 收藏0