For example, given the range [5, 7], you should return 4.
Naive Way: My first thought was to use "&" operation going though all numbers between m and n inclusively. That gets a TLE. I later wrote some test cases and find out that "&" operation is hard to keep even one bit when there is a gap between n and m.
For example: 4-8: 0100, 0101, 0110, 0111, 1000. result is 0000.
It turns out that m and n need to have same highest bit, otherwise the result will be 0.
I tried many times and finally find out that a method use only bit shift operation will do the trick. Any ">" or "<" compare condition will possibly ruin he algorithm because 0x80000000 is a negative number.
My method is a recursive one. The idea is keep finding highest bit of m, check if n has a higher bit. And let the recursive call do the rest bits.
public class Solution {
public int rangeBitwiseAnd(int m, int n) {
return rangeBitwiseAnd(m,n,0x80000000);
}
private int rangeBitwiseAnd(int m, int n, int shift){
// edge case
if(m==0) return 0;
// find highest bit of m
while((shift & m) == 0){
if((shift & n) != 0) return 0;
shift >>>= 1;
}
return shift + rangeBitwiseAnd(m - shift, n - shift, shift);
}
}
Improved Way: After viewing the Discuss, I find there are tons of lot better solutions.
One is from
int rangeBitwiseAnd(int m, int n) {
return (n > m) ? (rangeBitwiseAnd(m/2, n/2) << 1) : m;
}
Another is from
public int rangeBitwiseAnd(int m, int n) {
int count = 0;
while(m != n){
m >>= 1;
n >>= 1;
count++;
}
return m<<=count;
}
No comments:
Post a Comment