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.

**Understand the problem:**

We could take several examples, e.g. 5 6 7

101

110

111

-------

100

We could find out that the trick of the problem is when compare bit-by-bit for each number, once they are the same, e.g. bit 1 for the most significant bit, they start to be the same.

9 10 11 12

1001

1010

1011

1100

---------

1000

So the solution is shift both m and n to the right until they are the equal, count the number of steps it shifted. Then shift m left to the number of steps.

**Code (Java):**

public class Solution { public int rangeBitwiseAnd(int m, int n) { int shift = 0; while (m != n) { shift++; m = m >> 1; n = n >> 1; } return m << shift; } }

## No comments:

## Post a Comment