A Different bit solution (c++, 48ms)


  • 1
    D
    class Solution {
    public:
        int rangeBitwiseAnd(int m, int n) {
            int ans=0;
            for (int i=0; i<31; i++)
            {
                if (m&(1<<i) && n&(1<<i) && (n-m+1)<=(1<<i)) 
                {
                    ans = ans|(1<<i); 
                }
            }
            
            return ans;
        }
    };
    

    Idea:

    3210
    ↓↓↓↓
    0000
    0001
    0010
    0011
    0100
    0101
    0110
    0111
    1000
    1001
    1010
    1011
    1100
    1101
    1110
    1111
    

    The idea is, for ith bit, there should not be any 0 between m and n.
    The ith bit of m and ith bit of n must be 1 and the difference of m and n should be less than or equal to 2^i, that will ensure there is no 0 at ith bit between the numbers of m and n.


  • 0
    H

    "and the difference of m and n should be less than or equal to 2^i" -hw did yuh think that?


  • 0
    D

    If not, then there must be 0's. And you can not AND 0's. Think like this, at 3rd position, (i=2) there could be at most 4 (2^i) consecutive 1's. If the range have more than 4 values then there must be 0's.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.