LeetCode Bitwise AND of Numbers Range

· 262 words · 1 minute read
2017年7月
LeetCode

201. 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

方法

实际上就是求m和n的最左公共数字

那么我们可以用类似子网掩码的方式求，先初始化子网掩码，然后每次与m和n比较，若m与n跟子网掩码做的与操作后的数值不一样，那么子网掩码向左移一位，谨记最后返回时应是m&mask或者是n&mask若只是范围mask,那么当m = 0，同时n = 0时mask返回Integer.MAX_VALUE。

例如: m=1110001, n=1110111, 1110000则是答案.

补充 Integer.MAX_VALUE = 2^32 - 1

public class Solution {
    public int rangeBitwiseAnd(int m, int n) {
        int t = Integer.MAX_VALUE;
        while((m&t) != (n&t)){
            t = t << 1;
        }
        return m&t;
    }
}
Share