程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> leetcode筆記之Bitwise AND of Numbers Range解析

leetcode筆記之Bitwise AND of Numbers Range解析

編輯:C++入門知識

leetcode筆記之Bitwise AND of Numbers Range解析


一. 題目描述

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],其中 0 <= m <= n <= 2147483647,返回范圍內所有整數的按位與,包括邊界mn。比如給定范圍為[5, 7], 應返回4

單看題目描述,可以知道該題涉及到位運算,因此需動筆分析:

對於題目給定的范圍[5, 7],可寫為:

5: 101
6: 110  -> 100 -> 4
7: 111

再來兩個例子:

范圍[6, 8]:

6: 0110
7: 0111  -> 0000 -> 0
8: 1000

范圍[8, 10]:

8:  1000
9:  1001  -> 1000 -> 4
10: 1010

現在可以總結出規律了,對於范圍[m, n],若n的最高有效位比m的最高有效位要高,則必然會出現像例子出現的情況,必然在范圍內存在兩個數,這兩個數分別是對方的反碼:

6: 0110
7: 0111  -> 0000 -> 0
8: 1000

因此,只有當mn的最高有效位一致時,即m與n同時右移n位,且m == n,m == 1時按位與結果不為0,且該結果為mn的公共左邊首部,以下給出簡單的代碼:

三. 示例代碼

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

四. 小結

該題是數學問題,用位運算即可快速解決,主要是要找出規律。

   

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved