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は、境界mおよびnを含む範囲内のすべての整数のビット和を返す.例えば、与えられた範囲は[5, 7]であり、4に戻るべきである.
テーマの説明を見ると、この問題は所定の演算に関連していることがわかります.そのため、ペンを動かして分析する必要があります.
テーマに与えられた範囲[5,7]については、以下のように書くことができる.

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

もう2つの例を示します.
範囲[6,8]:

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

範囲[8,10]:

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

これで法則をまとめることができ、範囲[m, n]について、nの最高有効ビットがmの最高有効ビットより高いと、必然的に例のように現れる場合があり、必然的に範囲内に2つの数が存在し、この2つの数はそれぞれ相手の逆コードである.

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

したがって、mとnの最高有効ビットが一致する場合、すなわちmがnと同時にnビットを右にシフトし、m == n，m == 1の場合、ビットと結果は0ではなく、mとnの共通左ヘッダであり、以下に簡単なコードを与える.
三.サンプルコード

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

四.小結
この問題は数学の問題で、ビット演算で迅速に解決することができて、主に法則を探し出すことです.