[java/9ms] Inspired from BIT to find prefix, also explains the highly voted code.


  • 0

    The method is to find the same prefix, that is, the biggest number (a)(b) <= m, in which (b) are all zeroes and the last digit of (a) is one, and then return it.

    explanation: m and n has same prefix, then the result should be the prefix with trailing zeroes.

    Suppose, m = a0b, n = a1c, and a is the same prefix followed by the 1, thus a10..0 <= n, will set all digits behind the 1 to zero. Then we can use m to set the 1 to zero. That's how the highly voted code does.

    public int rangeBitwiseAnd(int m, int n) {
            int shift = 0;
            while(m != n){
                m >>= 1;
                n >>= 1;
                ++shift;
            }
            return m << shift;
        }
    

    But here, I use a different way.

    idx -= (idx & -idx). In this way, it will replace the last '1' to '0'.

    For instance [101010, 101101], we find the same prefix 101xxx and the range must contain 101100, which will set the last two digits to zero after AND. Also, since we have 101010 to set the third digit to zero, then we should return the prefix 101000.

    public int rangeBitwiseAnd(int m, int n) {
            while (m < n) n ^= (n & -n);
            return n;
        }
    

Log in to reply
 

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