201. Bitwise AND of Numbers Range

Question

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

Example 1:

Input: [5,7]
Output: 4

Example 2:

Input: [0,1]
Output: 0

Thinking:

• Method：这道题是求所有位的与，其中某一位出现过0则都为0
  • 11010　　11011　　11100　　11101　　11110
  • 实际上就是取最高位相同的位数。

class Solution {
    public int rangeBitwiseAnd(int m, int n) {
        int mask = ~0;
        while(m != n){
            mask <<= 1;
            m &= mask;
            n &= mask;
        }
        return m;
    }
}

二刷

class Solution {
    public int rangeBitwiseAnd(int m, int n) {
        int mask = ~0;
        while(m != n){
            m &= mask;
            n &= mask;
            mask <<= 1;
        }
        return m;
    }
}

Reference

1.[LeetCode] Bitwise AND of Numbers Range 数字范围位相与