Java solution, more complicated than smart ones here, understand at your own risk


  • 0
    A

    Algorithm explained in comments:

    public class Solution {
        public int rangeBitwiseAnd(int m, int n) {
            // algorithm: build a mapping table; for each digit, it is almost guaranteed to be 0, unless
            //  (1) the range [m,n] is small enough; (2)the small-range must fall into a fixed range
            // digit 1: must be 0 if number in range > 1 (2^0), otherwise the single number %2=1
            // digit 2: must be 0 if number in range > 2 (2^1), otherwise these two numbers %4=2,3
            // digit 3: must be 0 if number in range > 4 (2^2), otherwise these four numbers %8=4,5,6,7
            // digit 4: must be 0 if number in range > 8 (2^3), otherwise these 8 numbers %16=8,9,...,15
            //  ...
            // digit 31: must be 0 if number in range > 2^30, otherwise those numbers %(2^31)=2^30,...2^31-1
    
            int[] pow2 = new int[32];
            pow2[0] = 1;
            for (int index = 1; index <= 31; index++) {
                pow2[index] = pow2[index - 1] << 1;
            }
    
            int result = 0;
            // now check each bit to see whether we should make it 1
            for (int bit = 30; bit >= 0; bit--) {
                if (n - m + 1 <= pow2[bit]) {
                    int n_mod = n & (pow2[bit + 1] - 1);
                    int m_mod = m & (pow2[bit + 1] - 1);
                    if ((n_mod <= pow2[bit + 1] - 1 && n_mod >= pow2[bit])
                            && (m_mod <= pow2[bit + 1] - 1 && m_mod >= pow2[bit])) {
                        result |= pow2[bit];
                    }
                }
            }
    
            return result;
        }
    }

Log in to reply
 

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