- 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.
public class Solution {
public int rangeBitwiseAnd(int m, int n) {
if(m == n) return m;
return (int)restBits(n,m,30);
}
private long restBits(long upper,long lower,int idx){
if(idx < 0) return 0;
if(upper == lower) return lower;
long h1 = (upper >>> idx) & 1;
long h2 = (lower >>> idx) & 1;
long r1 = upper & (0xFFFFFFFF>>>(31-idx+1));
long r2 = lower & (0xFFFFFFFF>>>(31-idx+1));
if((h1 & h2) == 1){
return (1<<idx) + restBits(r1,r2,idx-1);
}
else if((h1 ^ h2) == 1){
return 0;
}
else{
return restBits(r1,r2,idx-1);
}
}
}
