Very neat and fast O(1) solution, with explain.


  • 0
    C

    First, let's consider 1, 2, we can tell that the first bits is 0. because it contains odd and even numbers.
    Similarly, for 4 consecutive numbers, the second bit must be 0.
    We will mask lower bits until (1<<shift) > range, where range = n - m;

    Above the range, they can be all in the 1 region, or they can be all in 0 region, for the bit of shift, or cross region. The trick here is that, we do not need to check all of the numbers, but only the minimum and maximum number.

    So, in the big picture, we only need to find the right position of a 0xFFFFFFFF<< shift mask. And the result should be n & m & ( 0xFFFFFFFF << shift). The blow method is still over complex, but I'll put it as is since it is AC.

    public int rangeBitwiseAnd(int m, int n) {
            int max = m & n;
            int range =  n - m;
            int bit = 1;
            int shift = 0;
            while(range >= (bit << shift)){
                shift++;
                if(shift > 31) return 0;
            }
            int screen = 0;
            while(shift <= 30 && (1<<shift)  <= max){
                screen |= (1<<shift);
                shift++;
            }
            return max & screen;
        }

Log in to reply
 

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