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.
Brutal force is to do AND operation for all numbers from m to n, this definitely will not pass time limit. There should be faster ways. From m to n, each number differs 1, so we know the left most couple bits should be same for all numbers from m to n. Thus we do right shift and find those common bits, and we get the answer.
public int rangeBitwiseAnd(int m, int n) { int pos = 0; while (m != n) { m = (m >> 1); n = (n >> 1); pos++; } return m << pos; }
No comments:
Post a Comment