LeetCode(201) 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.

ぶんせき

タイトルの字面の意味は2つの整数が閉区間を構成することを与えて、0<=m<=n<=2147483647はすべて合法的な整数で、区間内のすべての整数のビットと結果を求めます.
简単なテーマのように见えて、私达は直接一回遍歴して结果を得ることができて、复雑度はO(n)で、予想外のタイムアウト..
では、方法を変えて、再帰を採用してもいいですか?2段でそれぞれ結果を求めて、それから最終結果を得て、残念なことに再びTLE..
簡単には考えられないので、整数ごとのバイナリ表現を書いて分析してみてはいかがでしょうか.
5 0101 6 0110 7 0111 & 0100
どんな法則があるのか、結果の「1」はすべての数字の共有ビットであることがわかります.これにより効率的な解法が得られ,シフトの規則を用いて,数値の異なるビットを右にシフトし,シフトを必要とする個数を記録することができる.
詳細コードは次のセクションを参照してください.

ACコード

class Solution {
public:
    // ，  TLE
    int rangeBitwiseAnd1(int m, int n) {

        int ret = m;
        for (int i = m+1; i <= n; ++i)
        {
            ret = ret & i;
        }//for
        return ret;
    }

    // ， ，TLE again！
    int rangeBitwiseAnd2(int m, int n) {
        if (m == n)
            return m;

        int mid = (m + n) / 2;
        return rangeBitwiseAnd(m, mid) & rangeBitwiseAnd(mid + 1, n);
    }

    // ：
    int rangeBitwiseAnd(int m, int n) {
        int offset = 0;
        while (m && n)
        {
            // 
            if (m == n)
            {
                return m << offset;
            }
            m >>= 1;
            n >>= 1;
            offset++;
        }
        return 0;
    }
};

GitHubテストプログラムソースコード