Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

For example, given the range [5, 7], you should return 4.

Credits:

Special thanks to for adding this problem and creating all test cases.

 

 Analysis:

 

Find out the largest identical part starting from left of m and n, e.g.,

m = 20000, n=20218

1001110| 00100000

1001110| 10100000

Result:

1001110| 00000000

Solution:

public class Solution {    public int rangeBitwiseAnd(int m, int n) {        if (m>n || m==0) return 0;        if (m==n) return m;                int step =0;        while (m!=n){            m >>= 1;            n >>= 1;            step++;        }        return m<<=step;            }}

Solution 2:

If we do not know how to perform bit operator, we can still solve it like this:

public class Solution {    public int rangeBitwiseAnd(int m, int n) {        if (m>n || m==0) return 0;        if (m==n) return m;                StringBuilder mStr = new StringBuilder().append(Integer.toBinaryString(m));        StringBuilder base = new StringBuilder();        StringBuilder res = new StringBuilder();        for (int i=0;i
      
       baseVal){                    return Integer.parseInt(res.toString(),2);                } else {                    res.setCharAt(i,'1');                }            }        }        return Integer.parseInt(res.toString(),2);            }}