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

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

ReplyDelete