201. Bitwise AND of Numbers Range

Problem:

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:

    8  4  2  1
---------------
5 | 0  1  0  1
6 | 0  1  1  0
7 | 0  1  1  1

m has the fewest 1 prefix, n has the most 1 prefix. Need to find the common 1 prefix. So clear n's last 1 one by one until n <= m;

Solution:

class Solution {
    public int rangeBitwiseAnd(int m, int n) {
        while (n > m) {
            n = n & (n - 1);
        }
        return m & n;
    }
}