Bitwise AND of Numbers Range (LeetCode) 201

Question

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.

Solution

这道题思路如下

1. last bit of (odd number & even number) is 0.
2. when m != n, There is at least an odd number and an even number, so the last bit position result is 0.
3. Move m and n rigth a position.

Keep doing step 1,2,3 until m equal to n, use a factor to record the iteration time.

简单来说就是m和n的相同部分&得到的都是1，不同部分&都是0。当m和n不同时，相同部分在高位，因此每次同时向右移动1为去掉最低位的不同部分，直到剩下相同部分为止。用一个值记录移动了多少次，再将相同部分向左移动相同次数即可。

代码如下：

public class Solution {

public int rangeBitwiseAnd(int m, int n) {

int step = 0;

while (m != n) {

m >>= 1;

n >>= 1;

step++;

}

return m << step;

}

}