首页 > 代码库 > LeetCode-Bitwise AND of Numbers Range

LeetCode-Bitwise AND of Numbers Range

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 @amrsaqr 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<mStr.length();i++){            base.append(‘1‘);            res.append(‘0‘);        }                for (int i=0;i<mStr.length();i++){            if (mStr.charAt(i)==‘0‘){                base.setCharAt(i,‘0‘);            }            if (mStr.charAt(i)==‘1‘){                int baseVal = Integer.parseInt(base.toString(),2);                if (n>baseVal){                    return Integer.parseInt(res.toString(),2);                } else {                    res.setCharAt(i,‘1‘);                }            }        }        return Integer.parseInt(res.toString(),2);            }}

 

LeetCode-Bitwise AND of Numbers Range