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

### Analysis:

At the first glance, looping from m to n seems straightforward but obviously time-consuming.
Looping from number to number seems unavailable, but we can considering looping from bit to bit.
Let's first write down some binary numbers:

1    000001
2    000010
3    000011
4    000100
5    000101
6    000110
7    000111
8    001000

Let's consider each bit from low to high, we can observe that the lowest bit, is either 1 or 0 after a number of AND operation. In this problem, because the range is continuous, the only case that lowest bit will become 1 is when m==n, and the lowest bit is 1. In other words,  for the range [m, n], if n > m, the lowest bit is always 0. Why? Because either the lowest bit of m is 0 or 1, the lowest bit of (m AND m+1) must be 0.

Now we have get the lowest bit for final result, next step is to check the 2nd lowest bit. How to do it? Just using bit shifting!  m >> 1 and n >> 1 is all we need.

When to stop looping? Consider the case that:
m =  01000
n =   01011

(1)   01011 > 01000  ->  lowest bit = 0
(2)   0101 > 0100      ->  2nd lowest bit  = 0
(3)   010 = 010          ->  3rd lowest bit = current lowest bit  0
(4)   01 = 01              ->  4th lowest bit = current lowest bit   1
(5)   0 = 0                  ->  5th lowest bit = current lowest bit   0

Final result:   01000
We can see that step (3)-(5) is unnecessary, when m=n, the other bits are just the same as current m (or n), then we can easily get the final result.

The code below are writing in two fashions: using loop and recursion. The former is easy understand, while the later is neat and simple.

### Loop:Code(C++):

class Solution {
public:
int rangeBitwiseAnd(int m, int n) {
int k=0;
while (1) {
if (n>m){
k = k + 1;
}else{
return m << k;
}
m = m >> 1;
n = n >> 1;
}
return m;
}
};


### Code(Python):

class Solution:
# @param {integer} m
# @param {integer} n
# @return {integer}
def rangeBitwiseAnd(self, m, n):
k = 0
while True:
if n > m:
k += 1
else:
return m<<k
m = m >> 1
n = n >> 1



### Recursive:Code(C++):

class Solution {
public:
int rangeBitwiseAnd(int m, int n) {
if (n>m){
return rangeBitwiseAnd(m>>1, n>>1)<<1;
}else{
return m;
}
}
};


### Code(Python):

class Solution:
# @param {integer} m
# @param {integer} n
# @return {integer}
def rangeBitwiseAnd(self, m, n):
if n > m:
return self.rangeBitwiseAnd(m>>1, n>>1) << 1
else:
return m



#### 1 comment:

1. loved the explanation...but is there any proof for AND operations between range?