AdSense

Monday, October 3, 2016

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.

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