2 simple, concise, Java solutions: binary search (6ms) & bit op (9ms)


  • 0
    O

    In a nutshell, bit operation solution sweep worst case 32 steps, while binary search is worst case log2 (32) = 5 steps.

    Bit operation:

        public int rangeBitwiseAnd(int m, int n) {
            int tm = 0, tn = 0;
            for(int i = 0; i < 32; i++){
                tm = m >> i;
                tn = n >> i;
                if ( tm == 0 || tn == 0) 
                    return 0;
                if ( tm == tn) 
                    return tm << i;
                }
            return -1;
        }
    

    Binary search:

        public int rangeBitwiseAnd(int m, int n) {
            int start = 0;
            int end = 32;
            int mid = (start+end)/2;
            while (start < end){
                mid = (start+end)/2;
                if ((m >> mid) == (n >> mid)){
                    end = mid-1;
                } else {
                    start = mid+1;
                }
            }
            return (m >> start) << start;
        }
    
    

Log in to reply
 

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