201. 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.

Solution:

Observation from the example [5,7] =>4

101, 110, 111, the rightmost digit of bitwise and is 0 because of 110, we right shift all numbers by 1 position, the three numbers become 10, 11, 11 which are the same as 10, 11, again the rightmost digit is 0 because of 10, right shift all numbers and we get 1, 1, and the bitwise and is 1, so the result of [5,7] is 100 => 4. 

Keys: as long as n>m the rightmost digit must be 0. Because the rightmost digit differs by 1 for two neighbor numbers which means one of them must ended with 0 (is an even number). 

Then we can rightshift all numbers until m==n, and keep track how many bits we shifted. The result will be the final m plus the amount of 0 that we right shifted to make m==n.

 public int rangeBitwiseAnd(int m, int n) {  
     int count=0;  
     while((m>>count)!=(n>>count)) count++;  
     return m>>count<<count;  
   }