Labels

Monday, May 18, 2015

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.

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 applewolf, who find out that keep comparing from lower bits to higher bits can do the trick.


 int rangeBitwiseAnd(int m, int n) {  
   return (n > m) ? (rangeBitwiseAnd(m/2, n/2) << 1) : m;  
 }  

Another is from haw64, who find out that the result of AND operation is just left most consecutive common part of n and m (just two numbers, no need of numbers in between).

 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